blob: bbb4f2964347d42a8737119db436393a5da6d1bd [file] [log] [blame]
Dale Johannesen4dc35db2007-07-13 17:31:29 +00001//===----- SchedulePostRAList.cpp - list scheduler ------------------------===//
Dale Johannesen2182f062007-07-13 17:13:54 +00002//
3// The LLVM Compiler Infrastructure
4//
Chris Lattnerf3ebc3f2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Dale Johannesen2182f062007-07-13 17:13:54 +00007//
8//===----------------------------------------------------------------------===//
9//
10// This implements a top-down list scheduler, using standard algorithms.
11// The basic approach uses a priority queue of available nodes to schedule.
12// One at a time, nodes are taken from the priority queue (thus in priority
13// order), checked for legality to schedule, and emitted if legal.
14//
15// Nodes may not be legal to schedule either due to structural hazards (e.g.
16// pipeline or resource constraints) or because an input to the instruction has
17// not completed execution.
18//
19//===----------------------------------------------------------------------===//
20
Dale Johannesen2182f062007-07-13 17:13:54 +000021#include "llvm/CodeGen/Passes.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000022#include "AggressiveAntiDepBreaker.h"
23#include "AntiDepBreaker.h"
24#include "CriticalAntiDepBreaker.h"
25#include "llvm/ADT/BitVector.h"
26#include "llvm/ADT/Statistic.h"
27#include "llvm/Analysis/AliasAnalysis.h"
Dan Gohman60cb69e2008-11-19 23:18:57 +000028#include "llvm/CodeGen/LatencyPriorityQueue.h"
Dan Gohmandddc1ac2008-12-16 03:25:46 +000029#include "llvm/CodeGen/MachineDominators.h"
David Goodwinbe3039e2009-10-01 19:45:32 +000030#include "llvm/CodeGen/MachineFrameInfo.h"
Dale Johannesen2182f062007-07-13 17:13:54 +000031#include "llvm/CodeGen/MachineFunctionPass.h"
Dan Gohmandddc1ac2008-12-16 03:25:46 +000032#include "llvm/CodeGen/MachineLoopInfo.h"
Dan Gohmanad2134d2008-11-25 00:52:40 +000033#include "llvm/CodeGen/MachineRegisterInfo.h"
Andrew Trick05ff4662012-06-06 20:29:31 +000034#include "llvm/CodeGen/RegisterClassInfo.h"
Andrew Trick9a0c5832012-03-07 23:01:06 +000035#include "llvm/CodeGen/ScheduleDAGInstrs.h"
Dan Gohmanceac7c32009-01-16 01:33:36 +000036#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000037#include "llvm/CodeGen/SchedulerRegistry.h"
David Goodwine056d102009-10-26 22:31:16 +000038#include "llvm/Support/CommandLine.h"
Dale Johannesen2182f062007-07-13 17:13:54 +000039#include "llvm/Support/Debug.h"
Torok Edwin56d06592009-07-11 20:10:48 +000040#include "llvm/Support/ErrorHandling.h"
David Goodwinf20236a2009-08-11 01:44:26 +000041#include "llvm/Support/raw_ostream.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000042#include "llvm/Target/TargetInstrInfo.h"
43#include "llvm/Target/TargetLowering.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000044#include "llvm/Target/TargetRegisterInfo.h"
45#include "llvm/Target/TargetSubtargetInfo.h"
Dale Johannesen2182f062007-07-13 17:13:54 +000046using namespace llvm;
47
Chandler Carruth1b9dde02014-04-22 02:02:50 +000048#define DEBUG_TYPE "post-RA-sched"
49
Dan Gohmanceac7c32009-01-16 01:33:36 +000050STATISTIC(NumNoops, "Number of noops inserted");
Dan Gohman60cb69e2008-11-19 23:18:57 +000051STATISTIC(NumStalls, "Number of pipeline stalls");
David Goodwin83704852009-10-26 16:59:04 +000052STATISTIC(NumFixedAnti, "Number of fixed anti-dependencies");
Dan Gohman60cb69e2008-11-19 23:18:57 +000053
David Goodwin9a051a52009-10-01 21:46:35 +000054// Post-RA scheduling is enabled with
Evan Cheng0d639a22011-07-01 21:01:15 +000055// TargetSubtargetInfo.enablePostRAScheduler(). This flag can be used to
David Goodwin9a051a52009-10-01 21:46:35 +000056// override the target.
57static cl::opt<bool>
58EnablePostRAScheduler("post-RA-scheduler",
59 cl::desc("Enable scheduling after register allocation"),
David Goodwin1cc6dd92009-10-01 22:19:57 +000060 cl::init(false), cl::Hidden);
David Goodwin83704852009-10-26 16:59:04 +000061static cl::opt<std::string>
Dan Gohmanad2134d2008-11-25 00:52:40 +000062EnableAntiDepBreaking("break-anti-dependencies",
David Goodwin83704852009-10-26 16:59:04 +000063 cl::desc("Break post-RA scheduling anti-dependencies: "
64 "\"critical\", \"all\", or \"none\""),
65 cl::init("none"), cl::Hidden);
Dan Gohmanceac7c32009-01-16 01:33:36 +000066
David Goodwin7f651692009-09-01 18:34:03 +000067// If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod
68static cl::opt<int>
69DebugDiv("postra-sched-debugdiv",
70 cl::desc("Debug control MBBs that are scheduled"),
71 cl::init(0), cl::Hidden);
72static cl::opt<int>
73DebugMod("postra-sched-debugmod",
74 cl::desc("Debug control MBBs that are scheduled"),
75 cl::init(0), cl::Hidden);
76
David Goodwin661ea982009-10-26 19:41:00 +000077AntiDepBreaker::~AntiDepBreaker() { }
78
Dale Johannesen2182f062007-07-13 17:13:54 +000079namespace {
Nick Lewycky02d5f772009-10-25 06:33:48 +000080 class PostRAScheduler : public MachineFunctionPass {
Evan Cheng2d51c7c2010-06-18 23:09:54 +000081 const TargetInstrInfo *TII;
Jakob Stoklund Olesen4f5f84c2011-06-16 21:56:21 +000082 RegisterClassInfo RegClassInfo;
Dan Gohman87b02d52009-10-09 23:27:56 +000083
Dale Johannesen2182f062007-07-13 17:13:54 +000084 public:
85 static char ID;
Andrew Trickdf7e3762012-02-08 21:22:53 +000086 PostRAScheduler() : MachineFunctionPass(ID) {}
Dan Gohmanad2134d2008-11-25 00:52:40 +000087
Craig Topper4584cd52014-03-07 09:26:03 +000088 void getAnalysisUsage(AnalysisUsage &AU) const override {
Dan Gohman04023152009-07-31 23:37:33 +000089 AU.setPreservesCFG();
Chandler Carruth7b560d42015-09-09 17:55:00 +000090 AU.addRequired<AAResultsWrapperPass>();
Andrew Trickdf7e3762012-02-08 21:22:53 +000091 AU.addRequired<TargetPassConfig>();
Dan Gohmandddc1ac2008-12-16 03:25:46 +000092 AU.addRequired<MachineDominatorTree>();
93 AU.addPreserved<MachineDominatorTree>();
94 AU.addRequired<MachineLoopInfo>();
95 AU.addPreserved<MachineLoopInfo>();
96 MachineFunctionPass::getAnalysisUsage(AU);
97 }
98
Craig Topper4584cd52014-03-07 09:26:03 +000099 bool runOnMachineFunction(MachineFunction &Fn) override;
NAKAMURA Takumif51a34e2014-10-29 15:23:11 +0000100
Sanjay Patela2f658d2014-07-15 22:39:58 +0000101 bool enablePostRAScheduler(
102 const TargetSubtargetInfo &ST, CodeGenOpt::Level OptLevel,
103 TargetSubtargetInfo::AntiDepBreakMode &Mode,
104 TargetSubtargetInfo::RegClassVector &CriticalPathRCs) const;
Dale Johannesen2182f062007-07-13 17:13:54 +0000105 };
Dan Gohman60cb69e2008-11-19 23:18:57 +0000106 char PostRAScheduler::ID = 0;
107
Nick Lewycky02d5f772009-10-25 06:33:48 +0000108 class SchedulePostRATDList : public ScheduleDAGInstrs {
Dan Gohman60cb69e2008-11-19 23:18:57 +0000109 /// AvailableQueue - The priority queue to use for the available SUnits.
Dan Gohman682a2d12009-10-21 01:44:44 +0000110 ///
Dan Gohman60cb69e2008-11-19 23:18:57 +0000111 LatencyPriorityQueue AvailableQueue;
Jim Grosbachd772bde2010-05-14 21:19:48 +0000112
Dan Gohman60cb69e2008-11-19 23:18:57 +0000113 /// PendingQueue - This contains all of the instructions whose operands have
114 /// been issued, but their results are not ready yet (due to the latency of
115 /// the operation). Once the operands becomes available, the instruction is
116 /// added to the AvailableQueue.
117 std::vector<SUnit*> PendingQueue;
118
Dan Gohmanceac7c32009-01-16 01:33:36 +0000119 /// HazardRec - The hazard recognizer to use.
120 ScheduleHazardRecognizer *HazardRec;
121
David Goodwin83704852009-10-26 16:59:04 +0000122 /// AntiDepBreak - Anti-dependence breaking object, or NULL if none
123 AntiDepBreaker *AntiDepBreak;
124
Dan Gohman87b02d52009-10-09 23:27:56 +0000125 /// AA - AliasAnalysis for making memory reference queries.
126 AliasAnalysis *AA;
127
Andrew Trick60cf03e2012-03-07 05:21:52 +0000128 /// The schedule. Null SUnit*'s represent noop instructions.
129 std::vector<SUnit*> Sequence;
130
Krzysztof Parzyszek5c61d112016-03-05 15:45:23 +0000131 /// Ordered list of DAG postprocessing steps.
132 std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
133
Andrew Tricka53e1012013-08-23 17:48:33 +0000134 /// The index in BB of RegionEnd.
135 ///
136 /// This is the instruction number from the top of the current block, not
137 /// the SlotIndex. It is only used by the AntiDepBreaker.
138 unsigned EndIndex;
139
Dan Gohmanad2134d2008-11-25 00:52:40 +0000140 public:
Andrew Trick10ffc2b2010-12-24 05:03:26 +0000141 SchedulePostRATDList(
Alexey Samsonovea0aee62014-08-20 20:57:26 +0000142 MachineFunction &MF, MachineLoopInfo &MLI, AliasAnalysis *AA,
143 const RegisterClassInfo &,
144 TargetSubtargetInfo::AntiDepBreakMode AntiDepMode,
145 SmallVectorImpl<const TargetRegisterClass *> &CriticalPathRCs);
Dan Gohmanceac7c32009-01-16 01:33:36 +0000146
Alexander Kornienkof817c1c2015-04-11 02:11:45 +0000147 ~SchedulePostRATDList() override;
Dan Gohman60cb69e2008-11-19 23:18:57 +0000148
Andrew Trick52226d42012-03-07 23:00:49 +0000149 /// startBlock - Initialize register live-range state for scheduling in
Dan Gohmanb9543432009-02-10 23:27:53 +0000150 /// this block.
151 ///
Craig Topper4584cd52014-03-07 09:26:03 +0000152 void startBlock(MachineBasicBlock *BB) override;
Dan Gohmanb9543432009-02-10 23:27:53 +0000153
Andrew Tricka53e1012013-08-23 17:48:33 +0000154 // Set the index of RegionEnd within the current BB.
155 void setEndIndex(unsigned EndIdx) { EndIndex = EndIdx; }
156
Andrew Trick60cf03e2012-03-07 05:21:52 +0000157 /// Initialize the scheduler state for the next scheduling region.
Craig Topper4584cd52014-03-07 09:26:03 +0000158 void enterRegion(MachineBasicBlock *bb,
159 MachineBasicBlock::iterator begin,
160 MachineBasicBlock::iterator end,
161 unsigned regioninstrs) override;
Andrew Trick60cf03e2012-03-07 05:21:52 +0000162
163 /// Notify that the scheduler has finished scheduling the current region.
Craig Topper4584cd52014-03-07 09:26:03 +0000164 void exitRegion() override;
Andrew Trick60cf03e2012-03-07 05:21:52 +0000165
Dan Gohmanb9543432009-02-10 23:27:53 +0000166 /// Schedule - Schedule the instruction range using list scheduling.
167 ///
Craig Topper4584cd52014-03-07 09:26:03 +0000168 void schedule() override;
Jim Grosbachd772bde2010-05-14 21:19:48 +0000169
Andrew Tricke932bb72012-03-07 05:21:44 +0000170 void EmitSchedule();
171
Dan Gohman682a2d12009-10-21 01:44:44 +0000172 /// Observe - Update liveness information to account for the current
173 /// instruction, which will not be scheduled.
174 ///
Duncan P. N. Exon Smith5e6e8c72016-02-27 19:33:37 +0000175 void Observe(MachineInstr &MI, unsigned Count);
Dan Gohman682a2d12009-10-21 01:44:44 +0000176
Andrew Trick52226d42012-03-07 23:00:49 +0000177 /// finishBlock - Clean up register live-range state.
Dan Gohman682a2d12009-10-21 01:44:44 +0000178 ///
Craig Topper4584cd52014-03-07 09:26:03 +0000179 void finishBlock() override;
Dan Gohman682a2d12009-10-21 01:44:44 +0000180
Dan Gohman60cb69e2008-11-19 23:18:57 +0000181 private:
Krzysztof Parzyszek5c61d112016-03-05 15:45:23 +0000182 /// Apply each ScheduleDAGMutation step in order.
183 void postprocessDAG();
184
David Goodwin80a03cc2009-11-20 19:32:48 +0000185 void ReleaseSucc(SUnit *SU, SDep *SuccEdge);
186 void ReleaseSuccessors(SUnit *SU);
187 void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
188 void ListScheduleTopDown();
Jim Grosbachd772bde2010-05-14 21:19:48 +0000189
Andrew Trickedee68c2012-03-07 05:21:40 +0000190 void dumpSchedule() const;
Hal Finkel4fd3b1d2013-12-11 22:33:43 +0000191 void emitNoop(unsigned CurCycle);
Dan Gohman60cb69e2008-11-19 23:18:57 +0000192 };
Alexander Kornienkof00654e2015-06-23 09:49:53 +0000193}
Dale Johannesen2182f062007-07-13 17:13:54 +0000194
Andrew Trick1fa5bcb2012-02-08 21:23:13 +0000195char &llvm::PostRASchedulerID = PostRAScheduler::ID;
196
197INITIALIZE_PASS(PostRAScheduler, "post-RA-sched",
198 "Post RA top-down list latency scheduler", false, false)
199
Andrew Trick10ffc2b2010-12-24 05:03:26 +0000200SchedulePostRATDList::SchedulePostRATDList(
Alexey Samsonovea0aee62014-08-20 20:57:26 +0000201 MachineFunction &MF, MachineLoopInfo &MLI, AliasAnalysis *AA,
202 const RegisterClassInfo &RCI,
203 TargetSubtargetInfo::AntiDepBreakMode AntiDepMode,
204 SmallVectorImpl<const TargetRegisterClass *> &CriticalPathRCs)
Matthias Braun93563e72015-11-03 01:53:29 +0000205 : ScheduleDAGInstrs(MF, &MLI), AA(AA), EndIndex(0) {
Andrew Trick6b104f82013-12-28 21:56:55 +0000206
Eric Christopherd9134482014-08-04 21:25:23 +0000207 const InstrItineraryData *InstrItins =
Eric Christopherb66367a2014-10-14 07:17:23 +0000208 MF.getSubtarget().getInstrItineraryData();
Andrew Trick10ffc2b2010-12-24 05:03:26 +0000209 HazardRec =
Eric Christopherb66367a2014-10-14 07:17:23 +0000210 MF.getSubtarget().getInstrInfo()->CreateTargetPostRAHazardRecognizer(
Eric Christopherd9134482014-08-04 21:25:23 +0000211 InstrItins, this);
Krzysztof Parzyszek5c61d112016-03-05 15:45:23 +0000212 MF.getSubtarget().getPostRAMutations(Mutations);
Preston Gurd9a091472012-04-23 21:39:35 +0000213
214 assert((AntiDepMode == TargetSubtargetInfo::ANTIDEP_NONE ||
215 MRI.tracksLiveness()) &&
216 "Live-ins must be accurate for anti-dependency breaking");
Andrew Trick10ffc2b2010-12-24 05:03:26 +0000217 AntiDepBreak =
Evan Cheng0d639a22011-07-01 21:01:15 +0000218 ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_ALL) ?
Jakob Stoklund Olesen4f5f84c2011-06-16 21:56:21 +0000219 (AntiDepBreaker *)new AggressiveAntiDepBreaker(MF, RCI, CriticalPathRCs) :
Evan Cheng0d639a22011-07-01 21:01:15 +0000220 ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_CRITICAL) ?
Craig Topperc0196b12014-04-14 00:51:57 +0000221 (AntiDepBreaker *)new CriticalAntiDepBreaker(MF, RCI) : nullptr));
Andrew Trick10ffc2b2010-12-24 05:03:26 +0000222}
223
224SchedulePostRATDList::~SchedulePostRATDList() {
225 delete HazardRec;
226 delete AntiDepBreak;
227}
228
Andrew Trick60cf03e2012-03-07 05:21:52 +0000229/// Initialize state associated with the next scheduling region.
230void SchedulePostRATDList::enterRegion(MachineBasicBlock *bb,
231 MachineBasicBlock::iterator begin,
232 MachineBasicBlock::iterator end,
Andrew Tricka53e1012013-08-23 17:48:33 +0000233 unsigned regioninstrs) {
234 ScheduleDAGInstrs::enterRegion(bb, begin, end, regioninstrs);
Andrew Trick60cf03e2012-03-07 05:21:52 +0000235 Sequence.clear();
236}
237
238/// Print the schedule before exiting the region.
239void SchedulePostRATDList::exitRegion() {
240 DEBUG({
241 dbgs() << "*** Final schedule ***\n";
242 dumpSchedule();
243 dbgs() << '\n';
244 });
245 ScheduleDAGInstrs::exitRegion();
246}
247
Manman Ren19f49ac2012-09-11 22:23:19 +0000248#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
Andrew Trickedee68c2012-03-07 05:21:40 +0000249/// dumpSchedule - dump the scheduled Sequence.
250void SchedulePostRATDList::dumpSchedule() const {
251 for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
252 if (SUnit *SU = Sequence[i])
253 SU->dump(this);
254 else
255 dbgs() << "**** NOOP ****\n";
256 }
257}
Manman Ren742534c2012-09-06 19:06:06 +0000258#endif
Andrew Trickedee68c2012-03-07 05:21:40 +0000259
Sanjay Patela2f658d2014-07-15 22:39:58 +0000260bool PostRAScheduler::enablePostRAScheduler(
261 const TargetSubtargetInfo &ST,
262 CodeGenOpt::Level OptLevel,
263 TargetSubtargetInfo::AntiDepBreakMode &Mode,
264 TargetSubtargetInfo::RegClassVector &CriticalPathRCs) const {
265 Mode = ST.getAntiDepBreakMode();
266 ST.getCriticalPathRCs(CriticalPathRCs);
Matthias Braun39a2afc2015-06-13 03:42:16 +0000267 return ST.enablePostRAScheduler() &&
Sanjay Patela2f658d2014-07-15 22:39:58 +0000268 OptLevel >= ST.getOptLevelToEnablePostRAScheduler();
269}
270
Dan Gohman60cb69e2008-11-19 23:18:57 +0000271bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) {
Paul Robinson7c99ec52014-03-31 17:43:35 +0000272 if (skipOptnoneFunction(*Fn.getFunction()))
273 return false;
274
Eric Christopherfc6de422014-08-05 02:39:49 +0000275 TII = Fn.getSubtarget().getInstrInfo();
Andrew Trick10ffc2b2010-12-24 05:03:26 +0000276 MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>();
Chandler Carruth7b560d42015-09-09 17:55:00 +0000277 AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
Andrew Trickdf7e3762012-02-08 21:22:53 +0000278 TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();
279
Jakob Stoklund Olesen4f5f84c2011-06-16 21:56:21 +0000280 RegClassInfo.runOnMachineFunction(Fn);
Dan Gohman26e9b892009-10-10 00:15:38 +0000281
David Goodwin9a051a52009-10-01 21:46:35 +0000282 // Check for explicit enable/disable of post-ra scheduling.
Evan Cheng7fae11b2011-12-14 02:11:42 +0000283 TargetSubtargetInfo::AntiDepBreakMode AntiDepMode =
284 TargetSubtargetInfo::ANTIDEP_NONE;
Craig Topper760b1342012-02-22 05:59:10 +0000285 SmallVector<const TargetRegisterClass*, 4> CriticalPathRCs;
David Goodwin9a051a52009-10-01 21:46:35 +0000286 if (EnablePostRAScheduler.getPosition() > 0) {
287 if (!EnablePostRAScheduler)
Evan Cheng8b614762009-10-16 06:10:34 +0000288 return false;
David Goodwin9a051a52009-10-01 21:46:35 +0000289 } else {
Evan Cheng8b614762009-10-16 06:10:34 +0000290 // Check that post-RA scheduling is enabled for this target.
Andrew Trick10ffc2b2010-12-24 05:03:26 +0000291 // This may upgrade the AntiDepMode.
Eric Christopher3d4276f2015-01-27 07:31:29 +0000292 if (!enablePostRAScheduler(Fn.getSubtarget(), PassConfig->getOptLevel(),
Sanjay Patela2f658d2014-07-15 22:39:58 +0000293 AntiDepMode, CriticalPathRCs))
Evan Cheng8b614762009-10-16 06:10:34 +0000294 return false;
David Goodwin9a051a52009-10-01 21:46:35 +0000295 }
David Goodwin17199b52009-09-30 00:10:16 +0000296
David Goodwin02ad4cb2009-10-22 23:19:17 +0000297 // Check for antidep breaking override...
298 if (EnableAntiDepBreaking.getPosition() > 0) {
Evan Cheng0d639a22011-07-01 21:01:15 +0000299 AntiDepMode = (EnableAntiDepBreaking == "all")
300 ? TargetSubtargetInfo::ANTIDEP_ALL
301 : ((EnableAntiDepBreaking == "critical")
302 ? TargetSubtargetInfo::ANTIDEP_CRITICAL
303 : TargetSubtargetInfo::ANTIDEP_NONE);
David Goodwin02ad4cb2009-10-22 23:19:17 +0000304 }
305
David Greeneaa8ce382010-01-05 01:26:01 +0000306 DEBUG(dbgs() << "PostRAScheduler\n");
Dale Johannesen2182f062007-07-13 17:13:54 +0000307
Alexey Samsonovea0aee62014-08-20 20:57:26 +0000308 SchedulePostRATDList Scheduler(Fn, MLI, AA, RegClassInfo, AntiDepMode,
Andrew Trick10ffc2b2010-12-24 05:03:26 +0000309 CriticalPathRCs);
Dan Gohman619ef482009-01-15 19:20:50 +0000310
Dale Johannesen2182f062007-07-13 17:13:54 +0000311 // Loop over all of the basic blocks
Duncan P. N. Exon Smith1ff40982015-10-09 21:05:00 +0000312 for (auto &MBB : Fn) {
David Goodwin7f651692009-09-01 18:34:03 +0000313#ifndef NDEBUG
314 // If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod
315 if (DebugDiv > 0) {
316 static int bbcnt = 0;
317 if (bbcnt++ % DebugDiv != DebugMod)
318 continue;
Craig Toppera538d832012-08-22 06:07:19 +0000319 dbgs() << "*** DEBUG scheduling " << Fn.getName()
Duncan P. N. Exon Smith1ff40982015-10-09 21:05:00 +0000320 << ":BB#" << MBB.getNumber() << " ***\n";
David Goodwin7f651692009-09-01 18:34:03 +0000321 }
322#endif
323
Dan Gohmanb9543432009-02-10 23:27:53 +0000324 // Initialize register live-range state for scheduling in this block.
Duncan P. N. Exon Smith1ff40982015-10-09 21:05:00 +0000325 Scheduler.startBlock(&MBB);
Dan Gohmanb9543432009-02-10 23:27:53 +0000326
Dan Gohman5f8a2592009-01-16 22:10:20 +0000327 // Schedule each sequence of instructions not interrupted by a label
328 // or anything else that effectively needs to shut down scheduling.
Duncan P. N. Exon Smith1ff40982015-10-09 21:05:00 +0000329 MachineBasicBlock::iterator Current = MBB.end();
330 unsigned Count = MBB.size(), CurrentCount = Count;
331 for (MachineBasicBlock::iterator I = Current; I != MBB.begin();) {
Benjamin Kramerb6d0bd42014-03-02 12:27:27 +0000332 MachineInstr *MI = std::prev(I);
Andrew Tricka53e1012013-08-23 17:48:33 +0000333 --Count;
Jakob Stoklund Olesena793a592012-02-23 17:54:21 +0000334 // Calls are not scheduling boundaries before register allocation, but
335 // post-ra we don't gain anything by scheduling across calls since we
336 // don't need to worry about register pressure.
Duncan P. N. Exon Smith1ff40982015-10-09 21:05:00 +0000337 if (MI->isCall() || TII->isSchedulingBoundary(MI, &MBB, Fn)) {
338 Scheduler.enterRegion(&MBB, I, Current, CurrentCount - Count);
Andrew Tricka53e1012013-08-23 17:48:33 +0000339 Scheduler.setEndIndex(CurrentCount);
Andrew Trick52226d42012-03-07 23:00:49 +0000340 Scheduler.schedule();
Andrew Trick60cf03e2012-03-07 05:21:52 +0000341 Scheduler.exitRegion();
Dan Gohman25c16532010-05-01 00:01:06 +0000342 Scheduler.EmitSchedule();
Dan Gohmanb9543432009-02-10 23:27:53 +0000343 Current = MI;
Andrew Tricka53e1012013-08-23 17:48:33 +0000344 CurrentCount = Count;
Duncan P. N. Exon Smith5e6e8c72016-02-27 19:33:37 +0000345 Scheduler.Observe(*MI, CurrentCount);
Dan Gohman5f8a2592009-01-16 22:10:20 +0000346 }
Dan Gohmanb9543432009-02-10 23:27:53 +0000347 I = MI;
Evan Cheng7fae11b2011-12-14 02:11:42 +0000348 if (MI->isBundle())
349 Count -= MI->getBundleSize();
Dan Gohmand5643532009-02-03 18:57:45 +0000350 }
Dan Gohmandfaf6462009-02-11 04:27:20 +0000351 assert(Count == 0 && "Instruction count mismatch!");
Duncan P. N. Exon Smith1ff40982015-10-09 21:05:00 +0000352 assert((MBB.begin() == Current || CurrentCount != 0) &&
Dan Gohman64613ac2009-03-10 18:10:43 +0000353 "Instruction count mismatch!");
Duncan P. N. Exon Smith1ff40982015-10-09 21:05:00 +0000354 Scheduler.enterRegion(&MBB, MBB.begin(), Current, CurrentCount);
Andrew Tricka53e1012013-08-23 17:48:33 +0000355 Scheduler.setEndIndex(CurrentCount);
Andrew Trick52226d42012-03-07 23:00:49 +0000356 Scheduler.schedule();
Andrew Trick60cf03e2012-03-07 05:21:52 +0000357 Scheduler.exitRegion();
Dan Gohman25c16532010-05-01 00:01:06 +0000358 Scheduler.EmitSchedule();
Dan Gohmanb9543432009-02-10 23:27:53 +0000359
360 // Clean up register live-range state.
Andrew Trick52226d42012-03-07 23:00:49 +0000361 Scheduler.finishBlock();
David Goodwinae6bc822009-08-25 17:03:05 +0000362
David Goodwin6c08cfc2009-09-03 22:15:25 +0000363 // Update register kills
Duncan P. N. Exon Smith1ff40982015-10-09 21:05:00 +0000364 Scheduler.fixupKills(&MBB);
Dan Gohman60cb69e2008-11-19 23:18:57 +0000365 }
Dale Johannesen2182f062007-07-13 17:13:54 +0000366
367 return true;
368}
Jim Grosbachd772bde2010-05-14 21:19:48 +0000369
Dan Gohmanb9543432009-02-10 23:27:53 +0000370/// StartBlock - Initialize register live-range state for scheduling in
371/// this block.
Dan Gohmanad2134d2008-11-25 00:52:40 +0000372///
Andrew Trick52226d42012-03-07 23:00:49 +0000373void SchedulePostRATDList::startBlock(MachineBasicBlock *BB) {
Dan Gohmanb9543432009-02-10 23:27:53 +0000374 // Call the superclass.
Andrew Trick52226d42012-03-07 23:00:49 +0000375 ScheduleDAGInstrs::startBlock(BB);
Dan Gohmanad2134d2008-11-25 00:52:40 +0000376
David Goodwin83704852009-10-26 16:59:04 +0000377 // Reset the hazard recognizer and anti-dep breaker.
David Goodwin6021b4d2009-08-10 15:55:25 +0000378 HazardRec->Reset();
Craig Topperc0196b12014-04-14 00:51:57 +0000379 if (AntiDepBreak)
David Goodwin83704852009-10-26 16:59:04 +0000380 AntiDepBreak->StartBlock(BB);
Dan Gohmanb9543432009-02-10 23:27:53 +0000381}
382
383/// Schedule - Schedule the instruction range using list scheduling.
384///
Andrew Trick52226d42012-03-07 23:00:49 +0000385void SchedulePostRATDList::schedule() {
Dan Gohmanb9543432009-02-10 23:27:53 +0000386 // Build the scheduling graph.
Andrew Trick52226d42012-03-07 23:00:49 +0000387 buildSchedGraph(AA);
Dan Gohmanb9543432009-02-10 23:27:53 +0000388
Craig Topperc0196b12014-04-14 00:51:57 +0000389 if (AntiDepBreak) {
Jim Grosbachd772bde2010-05-14 21:19:48 +0000390 unsigned Broken =
Andrew Trick8c207e42012-03-09 04:29:02 +0000391 AntiDepBreak->BreakAntiDependencies(SUnits, RegionBegin, RegionEnd,
392 EndIndex, DbgValues);
Jim Grosbachd772bde2010-05-14 21:19:48 +0000393
David Goodwin80a03cc2009-11-20 19:32:48 +0000394 if (Broken != 0) {
Dan Gohmanb9543432009-02-10 23:27:53 +0000395 // We made changes. Update the dependency graph.
396 // Theoretically we could update the graph in place:
397 // When a live range is changed to use a different register, remove
398 // the def's anti-dependence *and* output-dependence edges due to
399 // that register, and add new anti-dependence and output-dependence
400 // edges based on the next live range of the register.
Andrew Trick60cf03e2012-03-07 05:21:52 +0000401 ScheduleDAG::clearDAG();
Andrew Trick52226d42012-03-07 23:00:49 +0000402 buildSchedGraph(AA);
Jim Grosbachd772bde2010-05-14 21:19:48 +0000403
David Goodwin83704852009-10-26 16:59:04 +0000404 NumFixedAnti += Broken;
Dan Gohmanb9543432009-02-10 23:27:53 +0000405 }
406 }
407
Krzysztof Parzyszekcd99e362016-03-08 16:54:20 +0000408 postprocessDAG();
409
David Greeneaa8ce382010-01-05 01:26:01 +0000410 DEBUG(dbgs() << "********** List Scheduling **********\n");
Matthias Braun9198c672015-11-06 20:59:02 +0000411 DEBUG(
412 for (const SUnit &SU : SUnits) {
413 SU.dumpAll(this);
414 dbgs() << '\n';
415 }
416 );
David Goodwin6021b4d2009-08-10 15:55:25 +0000417
Dan Gohmanb9543432009-02-10 23:27:53 +0000418 AvailableQueue.initNodes(SUnits);
David Goodwin80a03cc2009-11-20 19:32:48 +0000419 ListScheduleTopDown();
Dan Gohmanb9543432009-02-10 23:27:53 +0000420 AvailableQueue.releaseState();
421}
422
423/// Observe - Update liveness information to account for the current
424/// instruction, which will not be scheduled.
425///
Duncan P. N. Exon Smith5e6e8c72016-02-27 19:33:37 +0000426void SchedulePostRATDList::Observe(MachineInstr &MI, unsigned Count) {
Craig Topperc0196b12014-04-14 00:51:57 +0000427 if (AntiDepBreak)
Andrew Tricka316faa2012-03-07 23:00:52 +0000428 AntiDepBreak->Observe(MI, Count, EndIndex);
Dan Gohmanb9543432009-02-10 23:27:53 +0000429}
430
431/// FinishBlock - Clean up register live-range state.
432///
Andrew Trick52226d42012-03-07 23:00:49 +0000433void SchedulePostRATDList::finishBlock() {
Craig Topperc0196b12014-04-14 00:51:57 +0000434 if (AntiDepBreak)
David Goodwin83704852009-10-26 16:59:04 +0000435 AntiDepBreak->FinishBlock();
Dan Gohmanb9543432009-02-10 23:27:53 +0000436
437 // Call the superclass.
Andrew Trick52226d42012-03-07 23:00:49 +0000438 ScheduleDAGInstrs::finishBlock();
Dan Gohmanb9543432009-02-10 23:27:53 +0000439}
440
Krzysztof Parzyszek5c61d112016-03-05 15:45:23 +0000441/// Apply each ScheduleDAGMutation step in order.
442void SchedulePostRATDList::postprocessDAG() {
443 for (auto &M : Mutations)
444 M->apply(this);
445}
446
Dan Gohman60cb69e2008-11-19 23:18:57 +0000447//===----------------------------------------------------------------------===//
448// Top-Down Scheduling
449//===----------------------------------------------------------------------===//
450
451/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
Andrew Trickf1ff84c2012-11-12 19:28:57 +0000452/// the PendingQueue if the count reaches zero.
David Goodwin80a03cc2009-11-20 19:32:48 +0000453void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) {
Dan Gohman2d170892008-12-09 22:54:47 +0000454 SUnit *SuccSU = SuccEdge->getSUnit();
Reid Kleckner8ff5c192009-09-30 20:15:38 +0000455
Andrew Trick4b1f9e32012-11-13 02:35:06 +0000456 if (SuccEdge->isWeak()) {
Andrew Trickf1ff84c2012-11-12 19:28:57 +0000457 --SuccSU->WeakPredsLeft;
458 return;
459 }
Dan Gohman60cb69e2008-11-19 23:18:57 +0000460#ifndef NDEBUG
Reid Kleckner8ff5c192009-09-30 20:15:38 +0000461 if (SuccSU->NumPredsLeft == 0) {
David Greeneaa8ce382010-01-05 01:26:01 +0000462 dbgs() << "*** Scheduling failed! ***\n";
Dan Gohman60cb69e2008-11-19 23:18:57 +0000463 SuccSU->dump(this);
David Greeneaa8ce382010-01-05 01:26:01 +0000464 dbgs() << " has been released too many times!\n";
Craig Topperc0196b12014-04-14 00:51:57 +0000465 llvm_unreachable(nullptr);
Dan Gohman60cb69e2008-11-19 23:18:57 +0000466 }
467#endif
Reid Kleckner8ff5c192009-09-30 20:15:38 +0000468 --SuccSU->NumPredsLeft;
469
Andrew Trick84f9ad92011-05-06 18:14:32 +0000470 // Standard scheduler algorithms will recompute the depth of the successor
Andrew Trickaab77fe2011-05-06 17:09:08 +0000471 // here as such:
472 // SuccSU->setDepthToAtLeast(SU->getDepth() + SuccEdge->getLatency());
473 //
474 // However, we lazily compute node depth instead. Note that
475 // ScheduleNodeTopDown has already updated the depth of this node which causes
476 // all descendents to be marked dirty. Setting the successor depth explicitly
477 // here would cause depth to be recomputed for all its ancestors. If the
478 // successor is not yet ready (because of a transitively redundant edge) then
479 // this causes depth computation to be quadratic in the size of the DAG.
Jim Grosbachd772bde2010-05-14 21:19:48 +0000480
Dan Gohmanb9543432009-02-10 23:27:53 +0000481 // If all the node's predecessors are scheduled, this node is ready
482 // to be scheduled. Ignore the special ExitSU node.
483 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU)
Dan Gohman60cb69e2008-11-19 23:18:57 +0000484 PendingQueue.push_back(SuccSU);
Dan Gohmanb9543432009-02-10 23:27:53 +0000485}
486
487/// ReleaseSuccessors - Call ReleaseSucc on each of SU's successors.
David Goodwin80a03cc2009-11-20 19:32:48 +0000488void SchedulePostRATDList::ReleaseSuccessors(SUnit *SU) {
Dan Gohmanb9543432009-02-10 23:27:53 +0000489 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
David Goodwin8501dbbe2009-11-03 20:57:50 +0000490 I != E; ++I) {
David Goodwin80a03cc2009-11-20 19:32:48 +0000491 ReleaseSucc(SU, &*I);
David Goodwin8501dbbe2009-11-03 20:57:50 +0000492 }
Dan Gohman60cb69e2008-11-19 23:18:57 +0000493}
494
495/// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
496/// count of its successors. If a successor pending count is zero, add it to
497/// the Available queue.
David Goodwin80a03cc2009-11-20 19:32:48 +0000498void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
David Greeneaa8ce382010-01-05 01:26:01 +0000499 DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: ");
Dan Gohman60cb69e2008-11-19 23:18:57 +0000500 DEBUG(SU->dump(this));
Jim Grosbachd772bde2010-05-14 21:19:48 +0000501
Dan Gohman60cb69e2008-11-19 23:18:57 +0000502 Sequence.push_back(SU);
Jim Grosbachd772bde2010-05-14 21:19:48 +0000503 assert(CurCycle >= SU->getDepth() &&
David Goodwin8501dbbe2009-11-03 20:57:50 +0000504 "Node scheduled above its depth!");
David Goodwin80a03cc2009-11-20 19:32:48 +0000505 SU->setDepthToAtLeast(CurCycle);
Dan Gohman60cb69e2008-11-19 23:18:57 +0000506
David Goodwin80a03cc2009-11-20 19:32:48 +0000507 ReleaseSuccessors(SU);
Dan Gohman60cb69e2008-11-19 23:18:57 +0000508 SU->isScheduled = true;
Andrew Trick52226d42012-03-07 23:00:49 +0000509 AvailableQueue.scheduledNode(SU);
Dan Gohman60cb69e2008-11-19 23:18:57 +0000510}
511
Hal Finkel4fd3b1d2013-12-11 22:33:43 +0000512/// emitNoop - Add a noop to the current instruction sequence.
513void SchedulePostRATDList::emitNoop(unsigned CurCycle) {
514 DEBUG(dbgs() << "*** Emitting noop in cycle " << CurCycle << '\n');
515 HazardRec->EmitNoop();
Craig Topperc0196b12014-04-14 00:51:57 +0000516 Sequence.push_back(nullptr); // NULL here means noop
Hal Finkel4fd3b1d2013-12-11 22:33:43 +0000517 ++NumNoops;
518}
519
Dan Gohman60cb69e2008-11-19 23:18:57 +0000520/// ListScheduleTopDown - The main loop of list scheduling for top-down
521/// schedulers.
David Goodwin80a03cc2009-11-20 19:32:48 +0000522void SchedulePostRATDList::ListScheduleTopDown() {
Dan Gohman60cb69e2008-11-19 23:18:57 +0000523 unsigned CurCycle = 0;
Jim Grosbachd772bde2010-05-14 21:19:48 +0000524
David Goodwin8501dbbe2009-11-03 20:57:50 +0000525 // We're scheduling top-down but we're visiting the regions in
526 // bottom-up order, so we don't know the hazards at the start of a
527 // region. So assume no hazards (this should usually be ok as most
528 // blocks are a single region).
529 HazardRec->Reset();
530
Dan Gohmanb9543432009-02-10 23:27:53 +0000531 // Release any successors of the special Entry node.
David Goodwin80a03cc2009-11-20 19:32:48 +0000532 ReleaseSuccessors(&EntrySU);
Dan Gohmanb9543432009-02-10 23:27:53 +0000533
David Goodwin80a03cc2009-11-20 19:32:48 +0000534 // Add all leaves to Available queue.
Dan Gohman60cb69e2008-11-19 23:18:57 +0000535 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
536 // It is available if it has no predecessors.
Andrew Trickf1ff84c2012-11-12 19:28:57 +0000537 if (!SUnits[i].NumPredsLeft && !SUnits[i].isAvailable) {
Dan Gohman60cb69e2008-11-19 23:18:57 +0000538 AvailableQueue.push(&SUnits[i]);
539 SUnits[i].isAvailable = true;
540 }
541 }
Dan Gohmanb9543432009-02-10 23:27:53 +0000542
David Goodwin1f8c7a72009-08-12 21:47:46 +0000543 // In any cycle where we can't schedule any instructions, we must
544 // stall or emit a noop, depending on the target.
Benjamin Kramere3c9d232009-09-06 12:10:17 +0000545 bool CycleHasInsts = false;
David Goodwin1f8c7a72009-08-12 21:47:46 +0000546
Dan Gohman60cb69e2008-11-19 23:18:57 +0000547 // While Available queue is not empty, grab the node with the highest
548 // priority. If it is not ready put it back. Schedule the node.
Dan Gohmanceac7c32009-01-16 01:33:36 +0000549 std::vector<SUnit*> NotReady;
Dan Gohman60cb69e2008-11-19 23:18:57 +0000550 Sequence.reserve(SUnits.size());
551 while (!AvailableQueue.empty() || !PendingQueue.empty()) {
552 // Check to see if any of the pending instructions are ready to issue. If
553 // so, add them to the available queue.
Dan Gohmandddc1ac2008-12-16 03:25:46 +0000554 unsigned MinDepth = ~0u;
Dan Gohman60cb69e2008-11-19 23:18:57 +0000555 for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {
David Goodwin80a03cc2009-11-20 19:32:48 +0000556 if (PendingQueue[i]->getDepth() <= CurCycle) {
Dan Gohman60cb69e2008-11-19 23:18:57 +0000557 AvailableQueue.push(PendingQueue[i]);
558 PendingQueue[i]->isAvailable = true;
559 PendingQueue[i] = PendingQueue.back();
560 PendingQueue.pop_back();
561 --i; --e;
David Goodwin80a03cc2009-11-20 19:32:48 +0000562 } else if (PendingQueue[i]->getDepth() < MinDepth)
563 MinDepth = PendingQueue[i]->getDepth();
Dan Gohman60cb69e2008-11-19 23:18:57 +0000564 }
David Goodwinebd694b2009-08-11 17:35:23 +0000565
Andrew Trick10ffc2b2010-12-24 05:03:26 +0000566 DEBUG(dbgs() << "\n*** Examining Available\n"; AvailableQueue.dump(this));
David Goodwinebd694b2009-08-11 17:35:23 +0000567
Craig Topperc0196b12014-04-14 00:51:57 +0000568 SUnit *FoundSUnit = nullptr, *NotPreferredSUnit = nullptr;
Dan Gohmanceac7c32009-01-16 01:33:36 +0000569 bool HasNoopHazards = false;
570 while (!AvailableQueue.empty()) {
571 SUnit *CurSUnit = AvailableQueue.pop();
572
573 ScheduleHazardRecognizer::HazardType HT =
Andrew Trick10ffc2b2010-12-24 05:03:26 +0000574 HazardRec->getHazardType(CurSUnit, 0/*no stalls*/);
Dan Gohmanceac7c32009-01-16 01:33:36 +0000575 if (HT == ScheduleHazardRecognizer::NoHazard) {
Hal Finkel4fd3b1d2013-12-11 22:33:43 +0000576 if (HazardRec->ShouldPreferAnother(CurSUnit)) {
577 if (!NotPreferredSUnit) {
NAKAMURA Takumif51a34e2014-10-29 15:23:11 +0000578 // If this is the first non-preferred node for this cycle, then
579 // record it and continue searching for a preferred node. If this
580 // is not the first non-preferred node, then treat it as though
581 // there had been a hazard.
Hal Finkel4fd3b1d2013-12-11 22:33:43 +0000582 NotPreferredSUnit = CurSUnit;
583 continue;
584 }
585 } else {
586 FoundSUnit = CurSUnit;
587 break;
588 }
Dan Gohmanceac7c32009-01-16 01:33:36 +0000589 }
590
591 // Remember if this is a noop hazard.
592 HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard;
593
594 NotReady.push_back(CurSUnit);
595 }
596
Hal Finkel4fd3b1d2013-12-11 22:33:43 +0000597 // If we have a non-preferred node, push it back onto the available list.
598 // If we did not find a preferred node, then schedule this first
599 // non-preferred node.
600 if (NotPreferredSUnit) {
601 if (!FoundSUnit) {
602 DEBUG(dbgs() << "*** Will schedule a non-preferred instruction...\n");
603 FoundSUnit = NotPreferredSUnit;
604 } else {
605 AvailableQueue.push(NotPreferredSUnit);
606 }
607
Craig Topperc0196b12014-04-14 00:51:57 +0000608 NotPreferredSUnit = nullptr;
Hal Finkel4fd3b1d2013-12-11 22:33:43 +0000609 }
610
Dan Gohmanceac7c32009-01-16 01:33:36 +0000611 // Add the nodes that aren't ready back onto the available list.
612 if (!NotReady.empty()) {
613 AvailableQueue.push_all(NotReady);
614 NotReady.clear();
615 }
616
David Goodwin8501dbbe2009-11-03 20:57:50 +0000617 // If we found a node to schedule...
Dan Gohman60cb69e2008-11-19 23:18:57 +0000618 if (FoundSUnit) {
Hal Finkel4fd3b1d2013-12-11 22:33:43 +0000619 // If we need to emit noops prior to this instruction, then do so.
620 unsigned NumPreNoops = HazardRec->PreEmitNoops(FoundSUnit);
621 for (unsigned i = 0; i != NumPreNoops; ++i)
622 emitNoop(CurCycle);
623
David Goodwin8501dbbe2009-11-03 20:57:50 +0000624 // ... schedule the node...
David Goodwin80a03cc2009-11-20 19:32:48 +0000625 ScheduleNodeTopDown(FoundSUnit, CurCycle);
Dan Gohmanceac7c32009-01-16 01:33:36 +0000626 HazardRec->EmitInstruction(FoundSUnit);
Benjamin Kramere3c9d232009-09-06 12:10:17 +0000627 CycleHasInsts = true;
Andrew Trick18c9b372011-06-01 03:27:56 +0000628 if (HazardRec->atIssueLimit()) {
629 DEBUG(dbgs() << "*** Max instructions per cycle " << CurCycle << '\n');
630 HazardRec->AdvanceCycle();
631 ++CurCycle;
632 CycleHasInsts = false;
633 }
Dan Gohmanceac7c32009-01-16 01:33:36 +0000634 } else {
Benjamin Kramere3c9d232009-09-06 12:10:17 +0000635 if (CycleHasInsts) {
David Greeneaa8ce382010-01-05 01:26:01 +0000636 DEBUG(dbgs() << "*** Finished cycle " << CurCycle << '\n');
David Goodwin1f8c7a72009-08-12 21:47:46 +0000637 HazardRec->AdvanceCycle();
638 } else if (!HasNoopHazards) {
639 // Otherwise, we have a pipeline stall, but no other problem,
640 // just advance the current cycle and try again.
David Greeneaa8ce382010-01-05 01:26:01 +0000641 DEBUG(dbgs() << "*** Stall in cycle " << CurCycle << '\n');
David Goodwin1f8c7a72009-08-12 21:47:46 +0000642 HazardRec->AdvanceCycle();
David Goodwin80a03cc2009-11-20 19:32:48 +0000643 ++NumStalls;
David Goodwin1f8c7a72009-08-12 21:47:46 +0000644 } else {
645 // Otherwise, we have no instructions to issue and we have instructions
646 // that will fault if we don't do this right. This is the case for
647 // processors without pipeline interlocks and other cases.
Hal Finkel4fd3b1d2013-12-11 22:33:43 +0000648 emitNoop(CurCycle);
David Goodwin1f8c7a72009-08-12 21:47:46 +0000649 }
650
Dan Gohmanceac7c32009-01-16 01:33:36 +0000651 ++CurCycle;
Benjamin Kramere3c9d232009-09-06 12:10:17 +0000652 CycleHasInsts = false;
Dan Gohman60cb69e2008-11-19 23:18:57 +0000653 }
654 }
655
656#ifndef NDEBUG
Andrew Trick46a58662012-03-07 05:21:36 +0000657 unsigned ScheduledNodes = VerifyScheduledDAG(/*isBottomUp=*/false);
658 unsigned Noops = 0;
659 for (unsigned i = 0, e = Sequence.size(); i != e; ++i)
660 if (!Sequence[i])
661 ++Noops;
662 assert(Sequence.size() - Noops == ScheduledNodes &&
663 "The number of nodes scheduled doesn't match the expected number!");
664#endif // NDEBUG
Dan Gohman60cb69e2008-11-19 23:18:57 +0000665}
Andrew Tricke932bb72012-03-07 05:21:44 +0000666
667// EmitSchedule - Emit the machine code in scheduled order.
668void SchedulePostRATDList::EmitSchedule() {
Andrew Trick8c207e42012-03-09 04:29:02 +0000669 RegionBegin = RegionEnd;
Andrew Tricke932bb72012-03-07 05:21:44 +0000670
671 // If first instruction was a DBG_VALUE then put it back.
672 if (FirstDbgValue)
Andrew Trick8c207e42012-03-09 04:29:02 +0000673 BB->splice(RegionEnd, BB, FirstDbgValue);
Andrew Tricke932bb72012-03-07 05:21:44 +0000674
675 // Then re-insert them according to the given schedule.
676 for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
677 if (SUnit *SU = Sequence[i])
Andrew Trick8c207e42012-03-09 04:29:02 +0000678 BB->splice(RegionEnd, BB, SU->getInstr());
Andrew Tricke932bb72012-03-07 05:21:44 +0000679 else
680 // Null SUnit* is a noop.
Andrew Trick8c207e42012-03-09 04:29:02 +0000681 TII->insertNoop(*BB, RegionEnd);
Andrew Tricke932bb72012-03-07 05:21:44 +0000682
683 // Update the Begin iterator, as the first instruction in the block
684 // may have been scheduled later.
685 if (i == 0)
Benjamin Kramerb6d0bd42014-03-02 12:27:27 +0000686 RegionBegin = std::prev(RegionEnd);
Andrew Tricke932bb72012-03-07 05:21:44 +0000687 }
688
689 // Reinsert any remaining debug_values.
690 for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator
691 DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) {
Benjamin Kramerb6d0bd42014-03-02 12:27:27 +0000692 std::pair<MachineInstr *, MachineInstr *> P = *std::prev(DI);
Andrew Tricke932bb72012-03-07 05:21:44 +0000693 MachineInstr *DbgValue = P.first;
694 MachineBasicBlock::iterator OrigPrivMI = P.second;
695 BB->splice(++OrigPrivMI, BB, DbgValue);
696 }
697 DbgValues.clear();
Craig Topperc0196b12014-04-14 00:51:57 +0000698 FirstDbgValue = nullptr;
Andrew Tricke932bb72012-03-07 05:21:44 +0000699}