1//===- MachineScheduler.h - MachineInstr Scheduling Pass --------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file provides an interface for customizing the standard MachineScheduler
10// pass. Note that the entire pass may be replaced as follows:
11//
12// <Target>TargetMachine::createPassConfig(PassManagerBase &PM) {
13// PM.substitutePass(&MachineSchedulerID, &CustomSchedulerPassID);
14// ...}
15//
16// The MachineScheduler pass is only responsible for choosing the regions to be
17// scheduled. Targets can override the DAG builder and scheduler without
18// replacing the pass as follows:
19//
20// ScheduleDAGInstrs *<Target>TargetMachine::
21// createMachineScheduler(MachineSchedContext *C) {
22// return new CustomMachineScheduler(C);
23// }
24//
25// The default scheduler, ScheduleDAGMILive, builds the DAG and drives list
26// scheduling while updating the instruction stream, register pressure, and live
27// intervals. Most targets don't need to override the DAG builder and list
28// scheduler, but subtargets that require custom scheduling heuristics may
29// plugin an alternate MachineSchedStrategy. The strategy is responsible for
30// selecting the highest priority node from the list:
31//
32// ScheduleDAGInstrs *<Target>TargetMachine::
33// createMachineScheduler(MachineSchedContext *C) {
34// return new ScheduleDAGMILive(C, CustomStrategy(C));
35// }
36//
37// The DAG builder can also be customized in a sense by adding DAG mutations
38// that will run after DAG building and before list scheduling. DAG mutations
39// can adjust dependencies based on target-specific knowledge or add weak edges
40// to aid heuristics:
41//
42// ScheduleDAGInstrs *<Target>TargetMachine::
43// createMachineScheduler(MachineSchedContext *C) {
44// ScheduleDAGMI *DAG = createSchedLive(C);
45// DAG->addMutation(new CustomDAGMutation(...));
46// return DAG;
47// }
48//
49// A target that supports alternative schedulers can use the
50// MachineSchedRegistry to allow command line selection. This can be done by
51// implementing the following boilerplate:
52//
53// static ScheduleDAGInstrs *createCustomMachineSched(MachineSchedContext *C) {
54// return new CustomMachineScheduler(C);
55// }
56// static MachineSchedRegistry
57// SchedCustomRegistry("custom", "Run my target's custom scheduler",
58// createCustomMachineSched);
59//
60//
61// Finally, subtargets that don't need to implement custom heuristics but would
62// like to configure the GenericScheduler's policy for a given scheduler region,
63// including scheduling direction and register pressure tracking policy, can do
64// this:
65//
66// void <SubTarget>Subtarget::
67// overrideSchedPolicy(MachineSchedPolicy &Policy,
68// const SchedRegion &Region) const {
69// Policy.<Flag> = true;
70// }
71//
72//===----------------------------------------------------------------------===//
73
74#ifndef LLVM_CODEGEN_MACHINESCHEDULER_H
75#define LLVM_CODEGEN_MACHINESCHEDULER_H
76
77#include "llvm/ADT/APInt.h"
78#include "llvm/ADT/ArrayRef.h"
79#include "llvm/ADT/BitVector.h"
80#include "llvm/ADT/STLExtras.h"
81#include "llvm/ADT/SmallVector.h"
82#include "llvm/ADT/StringRef.h"
83#include "llvm/ADT/Twine.h"
84#include "llvm/CodeGen/AntiDepBreaker.h"
85#include "llvm/CodeGen/MachineBasicBlock.h"
86#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
87#include "llvm/CodeGen/MachinePassRegistry.h"
88#include "llvm/CodeGen/RegisterPressure.h"
89#include "llvm/CodeGen/ScheduleDAG.h"
90#include "llvm/CodeGen/ScheduleDAGInstrs.h"
91#include "llvm/CodeGen/ScheduleDAGMutation.h"
92#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
93#include "llvm/CodeGen/TargetSchedule.h"
94#include "llvm/Support/CommandLine.h"
95#include "llvm/Support/Compiler.h"
96#include "llvm/Support/ErrorHandling.h"
97#include <algorithm>
98#include <cassert>
99#include <list>
100#include <llvm/Support/raw_ostream.h>
101#include <memory>
102#include <string>
103#include <vector>
104
105namespace llvm {
106namespace impl_detail {
107// FIXME: Remove these declarations once RegisterClassInfo is queryable as an
108// analysis.
109class MachineSchedulerImpl;
110class SSAMachineSchedulerImpl;
111class PostMachineSchedulerImpl;
112} // namespace impl_detail
113
114namespace MISched {
115enum Direction {
116 Unspecified,
117 TopDown,
118 BottomUp,
119 Bidirectional,
120};
121} // namespace MISched
122
123/// Returns -misched-prera-direction.
124LLVM_ABI MISched::Direction getPreRADirection();
125/// Returns -misched-postra-break-antideps.
126LLVM_ABI TargetSubtargetInfo::AntiDepBreakMode getPostRABreakAntiDeps();
127/// Returns whether -verify-misched is set.
128LLVM_ABI bool shouldVerifyScheduling();
129
130#ifndef NDEBUG
131extern cl::opt<bool> ViewMISchedDAGs;
132extern cl::opt<bool> PrintDAGs;
133#else
134LLVM_ABI extern const bool ViewMISchedDAGs;
135LLVM_ABI extern const bool PrintDAGs;
136#endif
137
138class AAResults;
139class LiveIntervals;
140class MachineFunction;
141class MachineInstr;
142class MachineLoopInfo;
143class RegisterClassInfo;
144class SchedDFSResult;
145class TargetInstrInfo;
146class TargetPassConfig;
147class TargetRegisterInfo;
148
149/// MachineSchedContext provides enough context from the MachineScheduler pass
150/// for the target to instantiate a scheduler.
151struct LLVM_ABI MachineSchedContext {
152 MachineFunction *MF = nullptr;
153 const MachineLoopInfo *MLI = nullptr;
154 const TargetMachine *TM = nullptr;
155 AAResults *AA = nullptr;
156 LiveIntervals *LIS = nullptr;
157 MachineBlockFrequencyInfo *MBFI = nullptr;
158
159 RegisterClassInfo *RegClassInfo = nullptr;
160
161 MachineSchedContext();
162 MachineSchedContext &operator=(const MachineSchedContext &other) = delete;
163 MachineSchedContext(const MachineSchedContext &other) = delete;
164 virtual ~MachineSchedContext();
165};
166
167/// MachineSchedRegistry provides a selection of available machine instruction
168/// schedulers.
169class MachineSchedRegistry
170 : public MachinePassRegistryNode<
171 ScheduleDAGInstrs *(*)(MachineSchedContext *)> {
172public:
173 using ScheduleDAGCtor = ScheduleDAGInstrs *(*)(MachineSchedContext *);
174
175 // RegisterPassParser requires a (misnamed) FunctionPassCtor type.
176 using FunctionPassCtor = ScheduleDAGCtor;
177
178 LLVM_ABI static MachinePassRegistry<ScheduleDAGCtor> Registry;
179
180 MachineSchedRegistry(const char *N, const char *D, ScheduleDAGCtor C)
181 : MachinePassRegistryNode(N, D, C) {
182 Registry.Add(Node: this);
183 }
184
185 ~MachineSchedRegistry() { Registry.Remove(Node: this); }
186
187 // Accessors.
188 //
189 MachineSchedRegistry *getNext() const {
190 return (MachineSchedRegistry *)MachinePassRegistryNode::getNext();
191 }
192
193 static MachineSchedRegistry *getList() {
194 return (MachineSchedRegistry *)Registry.getList();
195 }
196
197 static void setListener(MachinePassRegistryListener<FunctionPassCtor> *L) {
198 Registry.setListener(L);
199 }
200};
201
202class ScheduleDAGMI;
203
204/// Define a generic scheduling policy for targets that don't provide their own
205/// MachineSchedStrategy. This can be overriden for each scheduling region
206/// before building the DAG.
207struct MachineSchedPolicy {
208 // Allow the scheduler to disable register pressure tracking.
209 bool ShouldTrackPressure = false;
210 /// Track LaneMasks to allow reordering of independent subregister writes
211 /// of the same vreg. \sa MachineSchedStrategy::shouldTrackLaneMasks()
212 bool ShouldTrackLaneMasks = false;
213
214 // Allow the scheduler to force top-down or bottom-up scheduling. If neither
215 // is true, the scheduler runs in both directions and converges.
216 bool OnlyTopDown = false;
217 bool OnlyBottomUp = false;
218
219 // Disable heuristic that tries to fetch nodes from long dependency chains
220 // first.
221 bool DisableLatencyHeuristic = false;
222
223 // Compute DFSResult for use in scheduling heuristics.
224 bool ComputeDFSResult = false;
225
226 // If enabled, some extra cases of physreg defs will be biased towards user.
227 bool BiasPRegsExtra = false;
228
229 MachineSchedPolicy() = default;
230};
231
232/// A region of an MBB for scheduling.
233struct SchedRegion {
234 /// RegionBegin is the first instruction in the scheduling region, and
235 /// RegionEnd is either MBB->end() or the scheduling boundary after the
236 /// last instruction in the scheduling region. These iterators cannot refer
237 /// to instructions outside of the identified scheduling region because
238 /// those may be reordered before scheduling this region.
239 MachineBasicBlock::iterator RegionBegin;
240 MachineBasicBlock::iterator RegionEnd;
241 unsigned NumRegionInstrs;
242
243 SchedRegion(MachineBasicBlock::iterator B, MachineBasicBlock::iterator E,
244 unsigned N)
245 : RegionBegin(B), RegionEnd(E), NumRegionInstrs(N) {}
246};
247
248/// MachineSchedStrategy - Interface to the scheduling algorithm used by
249/// ScheduleDAGMI.
250///
251/// Initialization sequence:
252/// initPolicy -> shouldTrackPressure -> initialize(DAG) -> registerRoots
253class LLVM_ABI MachineSchedStrategy {
254 virtual void anchor();
255
256public:
257 virtual ~MachineSchedStrategy() = default;
258
259 /// Optionally override the per-region scheduling policy.
260 virtual void initPolicy(MachineBasicBlock::iterator Begin,
261 MachineBasicBlock::iterator End,
262 unsigned NumRegionInstrs) {}
263
264 virtual MachineSchedPolicy getPolicy() const { return {}; }
265 virtual void dumpPolicy() const {}
266
267 /// Check if pressure tracking is needed before building the DAG and
268 /// initializing this strategy. Called after initPolicy.
269 virtual bool shouldTrackPressure() const { return true; }
270
271 /// Returns true if lanemasks should be tracked. LaneMask tracking is
272 /// necessary to reorder independent subregister defs for the same vreg.
273 /// This has to be enabled in combination with shouldTrackPressure().
274 virtual bool shouldTrackLaneMasks() const { return false; }
275
276 // If this method returns true, handling of the scheduling regions
277 // themselves (in case of a scheduling boundary in MBB) will be done
278 // beginning with the topmost region of MBB.
279 virtual bool doMBBSchedRegionsTopDown() const { return false; }
280
281 /// Initialize the strategy after building the DAG for a new region.
282 virtual void initialize(ScheduleDAGMI *DAG) = 0;
283
284 /// Tell the strategy that MBB is about to be processed.
285 virtual void enterMBB(MachineBasicBlock *MBB) {};
286
287 /// Tell the strategy that current MBB is done.
288 virtual void leaveMBB() {};
289
290 /// Notify this strategy that all roots have been released (including those
291 /// that depend on EntrySU or ExitSU).
292 virtual void registerRoots() {}
293
294 /// Pick the next node to schedule, or return NULL. Set IsTopNode to true to
295 /// schedule the node at the top of the unscheduled region. Otherwise it will
296 /// be scheduled at the bottom.
297 virtual SUnit *pickNode(bool &IsTopNode) = 0;
298
299 /// Scheduler callback to notify that a new subtree is scheduled.
300 virtual void scheduleTree(unsigned SubtreeID) {}
301
302 /// Notify MachineSchedStrategy that ScheduleDAGMI has scheduled an
303 /// instruction and updated scheduled/remaining flags in the DAG nodes.
304 virtual void schedNode(SUnit *SU, bool IsTopNode) = 0;
305
306 /// When all predecessor dependencies have been resolved, free this node for
307 /// top-down scheduling.
308 virtual void releaseTopNode(SUnit *SU) = 0;
309
310 /// When all successor dependencies have been resolved, free this node for
311 /// bottom-up scheduling.
312 virtual void releaseBottomNode(SUnit *SU) = 0;
313};
314
315/// State for breaking physical-register anti-dependencies while scheduling a
316/// machine basic block after register allocation.
317class LLVM_ABI AntiDepState {
318 /// The selected breaker, or null when anti-dependency breaking is disabled.
319 std::unique_ptr<AntiDepBreaker> Breaker;
320
321 /// Instruction index of the current region's end in its basic block.
322 unsigned RegionEndIndex = 0;
323
324 /// Position from which boundary instructions are scanned for liveness.
325 MachineBasicBlock::iterator BoundaryScanPos;
326
327 /// Instruction index corresponding to `BoundaryScanPos`.
328 unsigned BoundaryScanIndex = 0;
329
330 /// Whether ScheduleDAGMI::schedule() processed the current region.
331 bool RegionProcessed = false;
332
333public:
334 AntiDepState(MachineSchedContext *C,
335 TargetSubtargetInfo::AntiDepBreakMode AntiDepMode);
336
337 void startBlock(MachineBasicBlock *MBB);
338
339 void finishBlock();
340
341 void enterRegion(MachineBasicBlock::iterator End);
342
343 void exitRegion(MachineBasicBlock::iterator Begin,
344 MachineBasicBlock::iterator End);
345
346 bool breakAntiDependencies(const std::vector<SUnit> &SUnits,
347 MachineBasicBlock::iterator Begin,
348 MachineBasicBlock::iterator End,
349 AntiDepBreaker::DbgValueVector &DbgValues);
350
351private:
352 void scanRangeBackwards(MachineBasicBlock::iterator From,
353 MachineBasicBlock::iterator To);
354};
355
356/// ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply
357/// schedules machine instructions according to the given MachineSchedStrategy
358/// without much extra book-keeping. This is the common functionality between
359/// PreRA and PostRA MachineScheduler.
360class LLVM_ABI ScheduleDAGMI : public ScheduleDAGInstrs {
361protected:
362 AAResults *AA;
363 LiveIntervals *LIS;
364 MachineBlockFrequencyInfo *MBFI;
365 std::unique_ptr<MachineSchedStrategy> SchedImpl;
366
367 /// State for optional post-RA anti-dependency breaking.
368 AntiDepState AntiDep;
369
370 /// Ordered list of DAG postprocessing steps.
371 std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
372
373 /// The top of the unscheduled zone.
374 MachineBasicBlock::iterator CurrentTop;
375
376 /// The bottom of the unscheduled zone.
377 MachineBasicBlock::iterator CurrentBottom;
378
379#if LLVM_ENABLE_ABI_BREAKING_CHECKS
380 /// The number of instructions scheduled so far. Used to cut off the
381 /// scheduler at the point determined by misched-cutoff.
382 unsigned NumInstrsScheduled = 0;
383#endif
384
385public:
386 ScheduleDAGMI(MachineSchedContext *C, std::unique_ptr<MachineSchedStrategy> S,
387 bool RemoveKillFlags)
388 : ScheduleDAGMI(C, std::move(S), RemoveKillFlags,
389 TargetSubtargetInfo::ANTIDEP_NONE) {}
390
391 /// Construct a post-RA scheduler with the requested anti-dependency mode.
392 ScheduleDAGMI(MachineSchedContext *C, std::unique_ptr<MachineSchedStrategy> S,
393 bool RemoveKillFlags,
394 TargetSubtargetInfo::AntiDepBreakMode AntiDepMode)
395 : ScheduleDAGInstrs(*C->MF, C->MLI, RemoveKillFlags), AA(C->AA),
396 LIS(C->LIS), MBFI(C->MBFI), SchedImpl(std::move(S)),
397 AntiDep(C, SchedImpl->doMBBSchedRegionsTopDown()
398 ? TargetSubtargetInfo::ANTIDEP_NONE
399 : AntiDepMode) {}
400
401 // Provide a vtable anchor
402 ~ScheduleDAGMI() override;
403
404 /// If this method returns true, handling of the scheduling regions
405 /// themselves (in case of a scheduling boundary in MBB) will be done
406 /// beginning with the topmost region of MBB.
407 bool doMBBSchedRegionsTopDown() const override {
408 return SchedImpl->doMBBSchedRegionsTopDown();
409 }
410
411 // Returns LiveIntervals instance for use in DAG mutators and such.
412 LiveIntervals *getLIS() const { return LIS; }
413
414 /// Return true if this DAG supports VReg liveness and RegPressure.
415 virtual bool hasVRegLiveness() const { return false; }
416
417 /// Add a postprocessing step to the DAG builder.
418 /// Mutations are applied in the order that they are added after normal DAG
419 /// building and before MachineSchedStrategy initialization.
420 ///
421 /// ScheduleDAGMI takes ownership of the Mutation object.
422 void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) {
423 if (Mutation)
424 Mutations.push_back(x: std::move(Mutation));
425 }
426
427 MachineBasicBlock::iterator top() const { return CurrentTop; }
428 MachineBasicBlock::iterator bottom() const { return CurrentBottom; }
429
430 /// Implement the ScheduleDAGInstrs interface for handling the next scheduling
431 /// region. This covers all instructions in a block, while schedule() may only
432 /// cover a subset.
433 void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin,
434 MachineBasicBlock::iterator end,
435 unsigned regioninstrs) override;
436
437 void exitRegion() override;
438
439 /// Implement ScheduleDAGInstrs interface for scheduling a sequence of
440 /// reorderable instructions.
441 void schedule() override;
442
443 void startBlock(MachineBasicBlock *bb) override;
444 void finishBlock() override;
445
446 /// Change the position of an instruction within the basic block and update
447 /// live ranges and region boundary iterators.
448 void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos);
449
450 void viewGraph(const Twine &Name, const Twine &Title) override;
451 void viewGraph() override;
452
453protected:
454 // Top-Level entry points for the schedule() driver...
455
456 /// Apply each ScheduleDAGMutation step in order. This allows different
457 /// instances of ScheduleDAGMI to perform custom DAG postprocessing.
458 void postProcessDAG();
459
460 /// Release ExitSU predecessors and setup scheduler queues.
461 void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots);
462
463 /// Update scheduler DAG and queues after scheduling an instruction.
464 void updateQueues(SUnit *SU, bool IsTopNode);
465
466 /// Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues.
467 void placeDebugValues();
468
469 /// dump the scheduled Sequence.
470 void dumpSchedule() const;
471 /// Print execution trace of the schedule top-down or bottom-up.
472 void dumpScheduleTraceTopDown() const;
473 void dumpScheduleTraceBottomUp() const;
474
475 // Lesser helpers...
476 bool checkSchedLimit();
477
478 void findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots,
479 SmallVectorImpl<SUnit*> &BotRoots);
480
481 void releaseSucc(SUnit *SU, SDep *SuccEdge);
482 void releaseSuccessors(SUnit *SU);
483 void releasePred(SUnit *SU, SDep *PredEdge);
484 void releasePredecessors(SUnit *SU);
485};
486
487/// ScheduleDAGMILive is an implementation of ScheduleDAGInstrs that schedules
488/// machine instructions while updating LiveIntervals and tracking regpressure.
489class LLVM_ABI ScheduleDAGMILive : public ScheduleDAGMI {
490protected:
491 RegisterClassInfo *RegClassInfo;
492
493 /// Information about DAG subtrees. If DFSResult is NULL, then SchedulerTrees
494 /// will be empty.
495 SchedDFSResult *DFSResult = nullptr;
496 BitVector ScheduledTrees;
497
498 MachineBasicBlock::iterator LiveRegionEnd;
499
500 /// Maps vregs to the SUnits of their uses in the current scheduling region.
501 VReg2SUnitMultiMap VRegUses;
502
503 // Map each SU to its summary of pressure changes. This array is updated for
504 // liveness during bottom-up scheduling. Top-down scheduling may proceed but
505 // has no affect on the pressure diffs.
506 PressureDiffs SUPressureDiffs;
507
508 /// Register pressure in this region computed by initRegPressure.
509 bool ShouldTrackPressure = false;
510 bool ShouldTrackLaneMasks = false;
511 IntervalPressure RegPressure;
512 RegPressureTracker RPTracker;
513
514 /// List of pressure sets that exceed the target's pressure limit before
515 /// scheduling, listed in increasing set ID order. Each pressure set is paired
516 /// with its max pressure in the currently scheduled regions.
517 std::vector<PressureChange> RegionCriticalPSets;
518
519 /// The top of the unscheduled zone.
520 IntervalPressure TopPressure;
521 RegPressureTracker TopRPTracker;
522
523 /// The bottom of the unscheduled zone.
524 IntervalPressure BotPressure;
525 RegPressureTracker BotRPTracker;
526
527public:
528 ScheduleDAGMILive(MachineSchedContext *C,
529 std::unique_ptr<MachineSchedStrategy> S)
530 : ScheduleDAGMI(C, std::move(S), /*RemoveKillFlags=*/false),
531 RegClassInfo(C->RegClassInfo), RPTracker(RegPressure),
532 TopRPTracker(TopPressure), BotRPTracker(BotPressure) {}
533
534 ~ScheduleDAGMILive() override;
535
536 /// Return true if this DAG supports VReg liveness and RegPressure.
537 bool hasVRegLiveness() const override { return true; }
538
539 /// Return true if register pressure tracking is enabled.
540 bool isTrackingPressure() const { return ShouldTrackPressure; }
541
542 /// Get current register pressure for the top scheduled instructions.
543 const IntervalPressure &getTopPressure() const { return TopPressure; }
544 const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; }
545
546 /// Get current register pressure for the bottom scheduled instructions.
547 const IntervalPressure &getBotPressure() const { return BotPressure; }
548 const RegPressureTracker &getBotRPTracker() const { return BotRPTracker; }
549
550 /// Get register pressure for the entire scheduling region before scheduling.
551 const IntervalPressure &getRegPressure() const { return RegPressure; }
552
553 const std::vector<PressureChange> &getRegionCriticalPSets() const {
554 return RegionCriticalPSets;
555 }
556
557 PressureDiff &getPressureDiff(const SUnit *SU) {
558 return SUPressureDiffs[SU->NodeNum];
559 }
560 const PressureDiff &getPressureDiff(const SUnit *SU) const {
561 return SUPressureDiffs[SU->NodeNum];
562 }
563
564 /// Compute a DFSResult after DAG building is complete, and before any
565 /// queue comparisons.
566 void computeDFSResult();
567
568 /// Return a non-null DFS result if the scheduling strategy initialized it.
569 const SchedDFSResult *getDFSResult() const { return DFSResult; }
570
571 BitVector &getScheduledTrees() { return ScheduledTrees; }
572
573 /// Implement the ScheduleDAGInstrs interface for handling the next scheduling
574 /// region. This covers all instructions in a block, while schedule() may only
575 /// cover a subset.
576 void enterRegion(MachineBasicBlock *bb,
577 MachineBasicBlock::iterator begin,
578 MachineBasicBlock::iterator end,
579 unsigned regioninstrs) override;
580
581 /// Implement ScheduleDAGInstrs interface for scheduling a sequence of
582 /// reorderable instructions.
583 void schedule() override;
584
585 /// Compute the cyclic critical path through the DAG.
586 unsigned computeCyclicCriticalPath();
587
588 void dump() const override;
589
590protected:
591 // Top-Level entry points for the schedule() driver...
592
593 /// Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking
594 /// enabled. This sets up three trackers. RPTracker will cover the entire DAG
595 /// region, TopTracker and BottomTracker will be initialized to the top and
596 /// bottom of the DAG region without covereing any unscheduled instruction.
597 void buildDAGWithRegPressure();
598
599 /// Release ExitSU predecessors and setup scheduler queues. Re-position
600 /// the Top RP tracker in case the region beginning has changed.
601 void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots);
602
603 /// Move an instruction and update register pressure.
604 void scheduleMI(SUnit *SU, bool IsTopNode);
605
606 // Lesser helpers...
607
608 void initRegPressure();
609
610 void updatePressureDiffs(ArrayRef<VRegMaskOrUnit> LiveUses);
611
612 void updateScheduledPressure(const SUnit *SU,
613 const std::vector<unsigned> &NewMaxPressure);
614
615 void collectVRegUses(SUnit &SU);
616};
617
618//===----------------------------------------------------------------------===//
619///
620/// Helpers for implementing custom MachineSchedStrategy classes. These take
621/// care of the book-keeping associated with list scheduling heuristics.
622///
623//===----------------------------------------------------------------------===//
624
625/// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience
626/// methods for pushing and removing nodes. ReadyQueue's are uniquely identified
627/// by an ID. SUnit::NodeQueueId is a mask of the ReadyQueues the SUnit is in.
628///
629/// This is a convenience class that may be used by implementations of
630/// MachineSchedStrategy.
631class ReadyQueue {
632 unsigned ID;
633 std::string Name;
634 std::vector<SUnit*> Queue;
635
636public:
637 ReadyQueue(unsigned id, const Twine &name): ID(id), Name(name.str()) {}
638
639 unsigned getID() const { return ID; }
640
641 StringRef getName() const { return Name; }
642
643 // SU is in this queue if it's NodeQueueID is a superset of this ID.
644 bool isInQueue(SUnit *SU) const { return (SU->NodeQueueId & ID); }
645
646 bool empty() const { return Queue.empty(); }
647
648 void clear() { Queue.clear(); }
649
650 unsigned size() const { return Queue.size(); }
651
652 using iterator = std::vector<SUnit*>::iterator;
653
654 iterator begin() { return Queue.begin(); }
655
656 iterator end() { return Queue.end(); }
657
658 ArrayRef<SUnit*> elements() { return Queue; }
659
660 iterator find(SUnit *SU) { return llvm::find(Range&: Queue, Val: SU); }
661
662 void push(SUnit *SU) {
663 Queue.push_back(x: SU);
664 SU->NodeQueueId |= ID;
665 }
666
667 iterator remove(iterator I) {
668 (*I)->NodeQueueId &= ~ID;
669 *I = Queue.back();
670 unsigned idx = I - Queue.begin();
671 Queue.pop_back();
672 return Queue.begin() + idx;
673 }
674
675 LLVM_ABI void dump() const;
676};
677
678/// Summarize the unscheduled region.
679struct SchedRemainder {
680 // Critical path through the DAG in expected latency.
681 unsigned CriticalPath;
682 unsigned CyclicCritPath;
683
684 // Scaled count of micro-ops left to schedule.
685 unsigned RemIssueCount;
686
687 bool IsAcyclicLatencyLimited;
688
689 // Unscheduled resources
690 SmallVector<unsigned, 16> RemainingCounts;
691
692 SchedRemainder() { reset(); }
693
694 void reset() {
695 CriticalPath = 0;
696 CyclicCritPath = 0;
697 RemIssueCount = 0;
698 IsAcyclicLatencyLimited = false;
699 RemainingCounts.clear();
700 }
701
702 LLVM_ABI void init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel);
703};
704
705/// ResourceSegments are a collection of intervals closed on the
706/// left and opened on the right:
707///
708/// list{ [a1, b1), [a2, b2), ..., [a_N, b_N) }
709///
710/// The collection has the following properties:
711///
712/// 1. The list is ordered: a_i < b_i and b_i < a_(i+1)
713///
714/// 2. The intervals in the collection do not intersect each other.
715///
716/// A \ref ResourceSegments instance represents the cycle
717/// reservation history of the instance of and individual resource.
718class ResourceSegments {
719public:
720 /// Represents an interval of discrete integer values closed on
721 /// the left and open on the right: [a, b).
722 typedef std::pair<int64_t, int64_t> IntervalTy;
723
724 /// Adds an interval [a, b) to the collection of the instance.
725 ///
726 /// When adding [a, b[ to the collection, the operation merges the
727 /// adjacent intervals. For example
728 ///
729 /// 0 1 2 3 4 5 6 7 8 9 10
730 /// [-----) [--) [--)
731 /// + [--)
732 /// = [-----------) [--)
733 ///
734 /// To be able to debug duplicate resource usage, the function has
735 /// assertion that checks that no interval should be added if it
736 /// overlaps any of the intervals in the collection. We can
737 /// require this because by definition a \ref ResourceSegments is
738 /// attached only to an individual resource instance.
739 LLVM_ABI void add(IntervalTy A, const unsigned CutOff = 10);
740
741public:
742 /// Checks whether intervals intersect.
743 LLVM_ABI static bool intersects(IntervalTy A, IntervalTy B);
744
745 /// These function return the interval used by a resource in bottom and top
746 /// scheduling.
747 ///
748 /// Consider an instruction that uses resources X0, X1 and X2 as follows:
749 ///
750 /// X0 X1 X1 X2 +--------+-------------+--------------+
751 /// |Resource|AcquireAtCycle|ReleaseAtCycle|
752 /// +--------+-------------+--------------+
753 /// | X0 | 0 | 1 |
754 /// +--------+-------------+--------------+
755 /// | X1 | 1 | 3 |
756 /// +--------+-------------+--------------+
757 /// | X2 | 3 | 4 |
758 /// +--------+-------------+--------------+
759 ///
760 /// If we can schedule the instruction at cycle C, we need to
761 /// compute the interval of the resource as follows:
762 ///
763 /// # TOP DOWN SCHEDULING
764 ///
765 /// Cycles scheduling flows to the _right_, in the same direction
766 /// of time.
767 ///
768 /// C 1 2 3 4 5 ...
769 /// ------|------|------|------|------|------|----->
770 /// X0 X1 X1 X2 ---> direction of time
771 /// X0 [C, C+1)
772 /// X1 [C+1, C+3)
773 /// X2 [C+3, C+4)
774 ///
775 /// Therefore, the formula to compute the interval for a resource
776 /// of an instruction that can be scheduled at cycle C in top-down
777 /// scheduling is:
778 ///
779 /// [C+AcquireAtCycle, C+ReleaseAtCycle)
780 ///
781 ///
782 /// # BOTTOM UP SCHEDULING
783 ///
784 /// Cycles scheduling flows to the _left_, in opposite direction
785 /// of time.
786 ///
787 /// In bottom up scheduling, the scheduling happens in opposite
788 /// direction to the execution of the cycles of the
789 /// instruction. When the instruction is scheduled at cycle `C`,
790 /// the resources are allocated in the past relative to `C`:
791 ///
792 /// 2 1 C -1 -2 -3 -4 -5 ...
793 /// <-----|------|------|------|------|------|------|------|---
794 /// X0 X1 X1 X2 ---> direction of time
795 /// X0 (C+1, C]
796 /// X1 (C, C-2]
797 /// X2 (C-2, C-3]
798 ///
799 /// Therefore, the formula to compute the interval for a resource
800 /// of an instruction that can be scheduled at cycle C in bottom-up
801 /// scheduling is:
802 ///
803 /// [C-ReleaseAtCycle+1, C-AcquireAtCycle+1)
804 ///
805 ///
806 /// NOTE: In both cases, the number of cycles booked by a
807 /// resources is the value (ReleaseAtCycle - AcquireAtCycle).
808 static IntervalTy getResourceIntervalBottom(unsigned C, unsigned AcquireAtCycle,
809 unsigned ReleaseAtCycle) {
810 return std::make_pair<long, long>(x: (long)C - (long)ReleaseAtCycle + 1L,
811 y: (long)C - (long)AcquireAtCycle + 1L);
812 }
813 static IntervalTy getResourceIntervalTop(unsigned C, unsigned AcquireAtCycle,
814 unsigned ReleaseAtCycle) {
815 return std::make_pair<long, long>(x: (long)C + (long)AcquireAtCycle,
816 y: (long)C + (long)ReleaseAtCycle);
817 }
818
819private:
820 /// Finds the first cycle in which a resource can be allocated.
821 ///
822 /// The function uses the \param IntervalBuider [*] to build a
823 /// resource interval [a, b[ out of the input parameters \param
824 /// CurrCycle, \param AcquireAtCycle and \param ReleaseAtCycle.
825 ///
826 /// The function then loops through the intervals in the ResourceSegments
827 /// and shifts the interval [a, b[ and the ReturnCycle to the
828 /// right until there is no intersection between the intervals of
829 /// the \ref ResourceSegments instance and the new shifted [a, b[. When
830 /// this condition is met, the ReturnCycle (which
831 /// correspond to the cycle in which the resource can be
832 /// allocated) is returned.
833 ///
834 /// c = CurrCycle in input
835 /// c 1 2 3 4 5 6 7 8 9 10 ... ---> (time
836 /// flow)
837 /// ResourceSegments... [---) [-------) [-----------)
838 /// c [1 3[ -> AcquireAtCycle=1, ReleaseAtCycle=3
839 /// ++c [1 3)
840 /// ++c [1 3)
841 /// ++c [1 3)
842 /// ++c [1 3)
843 /// ++c [1 3) ---> returns c
844 /// incremented by 5 (c+5)
845 ///
846 ///
847 /// Notice that for bottom-up scheduling the diagram is slightly
848 /// different because the current cycle c is always on the right
849 /// of the interval [a, b) (see \ref
850 /// `getResourceIntervalBottom`). This is because the cycle
851 /// increments for bottom-up scheduling moved in the direction
852 /// opposite to the direction of time:
853 ///
854 /// --------> direction of time.
855 /// XXYZZZ (resource usage)
856 /// --------> direction of top-down execution cycles.
857 /// <-------- direction of bottom-up execution cycles.
858 ///
859 /// Even though bottom-up scheduling moves against the flow of
860 /// time, the algorithm used to find the first free slot in between
861 /// intervals is the same as for top-down scheduling.
862 ///
863 /// [*] See \ref `getResourceIntervalTop` and
864 /// \ref `getResourceIntervalBottom` to see how such resource intervals
865 /// are built.
866 LLVM_ABI unsigned getFirstAvailableAt(
867 unsigned CurrCycle, unsigned AcquireAtCycle, unsigned ReleaseAtCycle,
868 std::function<IntervalTy(unsigned, unsigned, unsigned)> IntervalBuilder)
869 const;
870
871public:
872 /// getFirstAvailableAtFromBottom and getFirstAvailableAtFromTop
873 /// should be merged in a single function in which a function that
874 /// creates the `NewInterval` is passed as a parameter.
875 unsigned getFirstAvailableAtFromBottom(unsigned CurrCycle,
876 unsigned AcquireAtCycle,
877 unsigned ReleaseAtCycle) const {
878 return getFirstAvailableAt(CurrCycle, AcquireAtCycle, ReleaseAtCycle,
879 IntervalBuilder: getResourceIntervalBottom);
880 }
881 unsigned getFirstAvailableAtFromTop(unsigned CurrCycle,
882 unsigned AcquireAtCycle,
883 unsigned ReleaseAtCycle) const {
884 return getFirstAvailableAt(CurrCycle, AcquireAtCycle, ReleaseAtCycle,
885 IntervalBuilder: getResourceIntervalTop);
886 }
887
888private:
889 std::list<IntervalTy> _Intervals;
890 /// Merge all adjacent intervals in the collection. For all pairs
891 /// of adjacient intervals, it performs [a, b) + [b, c) -> [a, c).
892 ///
893 /// Before performing the merge operation, the intervals are
894 /// sorted with \ref sort_predicate.
895 LLVM_ABI void sortAndMerge();
896
897public:
898 // constructor for empty set
899 explicit ResourceSegments() = default;
900 bool empty() const { return _Intervals.empty(); }
901 explicit ResourceSegments(const std::list<IntervalTy> &Intervals)
902 : _Intervals(Intervals) {
903 sortAndMerge();
904 }
905
906 friend bool operator==(const ResourceSegments &c1,
907 const ResourceSegments &c2) {
908 return c1._Intervals == c2._Intervals;
909 }
910 friend llvm::raw_ostream &operator<<(llvm::raw_ostream &os,
911 const ResourceSegments &Segments) {
912 os << "{ ";
913 for (auto p : Segments._Intervals)
914 os << "[" << p.first << ", " << p.second << "), ";
915 os << "}\n";
916 return os;
917 }
918};
919
920/// Each Scheduling boundary is associated with ready queues. It tracks the
921/// current cycle in the direction of movement, and maintains the state
922/// of "hazards" and other interlocks at the current cycle.
923class SchedBoundary {
924public:
925 /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
926 enum {
927 TopQID = 1,
928 BotQID = 2,
929 LogMaxQID = 2
930 };
931
932 ScheduleDAGMI *DAG = nullptr;
933 const TargetSchedModel *SchedModel = nullptr;
934 SchedRemainder *Rem = nullptr;
935
936 ReadyQueue Available;
937 ReadyQueue Pending;
938
939 std::unique_ptr<ScheduleHazardRecognizer> HazardRec;
940
941private:
942 /// True if the pending Q should be checked/updated before scheduling another
943 /// instruction.
944 bool CheckPending;
945
946 /// Number of cycles it takes to issue the instructions scheduled in this
947 /// zone. It is defined as: scheduled-micro-ops / issue-width + stalls.
948 /// See getStalls().
949 unsigned CurrCycle;
950
951 /// Micro-ops issued in the current cycle
952 unsigned CurrMOps;
953
954 /// MinReadyCycle - Cycle of the soonest available instruction.
955 unsigned MinReadyCycle;
956
957 // The expected latency of the critical path in this scheduled zone.
958 unsigned ExpectedLatency;
959
960 // The latency of dependence chains leading into this zone.
961 // For each node scheduled bottom-up: DLat = max DLat, N.Depth.
962 // For each cycle scheduled: DLat -= 1.
963 unsigned DependentLatency;
964
965 /// Count the scheduled (issued) micro-ops that can be retired by
966 /// time=CurrCycle assuming the first scheduled instr is retired at time=0.
967 unsigned RetiredMOps;
968
969 // Count scheduled resources that have been executed. Resources are
970 // considered executed if they become ready in the time that it takes to
971 // saturate any resource including the one in question. Counts are scaled
972 // for direct comparison with other resources. Counts can be compared with
973 // MOps * getMicroOpFactor and Latency * getLatencyFactor.
974 SmallVector<unsigned, 16> ExecutedResCounts;
975
976 /// Cache the max count for a single resource.
977 unsigned MaxExecutedResCount;
978
979 // Cache the critical resources ID in this scheduled zone.
980 unsigned ZoneCritResIdx;
981
982 // Is the scheduled region resource limited vs. latency limited.
983 bool IsResourceLimited;
984
985public:
986private:
987 /// Record how resources have been allocated across the cycles of
988 /// the execution.
989 std::map<unsigned, ResourceSegments> ReservedResourceSegments;
990 std::vector<unsigned> ReservedCycles;
991 /// For each PIdx, stores first index into ReservedResourceSegments that
992 /// corresponds to it.
993 ///
994 /// For example, consider the following 3 resources (ResourceCount =
995 /// 3):
996 ///
997 /// +------------+--------+
998 /// |ResourceName|NumUnits|
999 /// +------------+--------+
1000 /// | X | 2 |
1001 /// +------------+--------+
1002 /// | Y | 3 |
1003 /// +------------+--------+
1004 /// | Z | 1 |
1005 /// +------------+--------+
1006 ///
1007 /// In this case, the total number of resource instances is 6. The
1008 /// vector \ref ReservedResourceSegments will have a slot for each instance.
1009 /// The vector \ref ReservedCyclesIndex will track at what index the first
1010 /// instance of the resource is found in the vector of \ref
1011 /// ReservedResourceSegments:
1012 ///
1013 /// Indexes of instances in
1014 /// ReservedResourceSegments
1015 ///
1016 /// 0 1 2 3 4 5
1017 /// ReservedCyclesIndex[0] = 0; [X0, X1,
1018 /// ReservedCyclesIndex[1] = 2; Y0, Y1, Y2
1019 /// ReservedCyclesIndex[2] = 5; Z
1020 SmallVector<unsigned, 16> ReservedCyclesIndex;
1021
1022 // For each PIdx, stores the resource group IDs of its subunits
1023 SmallVector<APInt, 16> ResourceGroupSubUnitMasks;
1024
1025#if LLVM_ENABLE_ABI_BREAKING_CHECKS
1026 // Remember the greatest possible stall as an upper bound on the number of
1027 // times we should retry the pending queue because of a hazard.
1028 unsigned MaxObservedStall;
1029#endif
1030
1031public:
1032 /// Pending queues extend the ready queues with the same ID and the
1033 /// PendingFlag set.
1034 SchedBoundary(unsigned ID, const Twine &Name):
1035 Available(ID, Name+".A"), Pending(ID << LogMaxQID, Name+".P") {
1036 reset();
1037 }
1038 SchedBoundary &operator=(const SchedBoundary &other) = delete;
1039 SchedBoundary(const SchedBoundary &other) = delete;
1040 LLVM_ABI ~SchedBoundary();
1041
1042 LLVM_ABI void reset();
1043
1044 LLVM_ABI void init(ScheduleDAGMI *dag, const TargetSchedModel *smodel,
1045 SchedRemainder *rem);
1046
1047 bool isTop() const {
1048 return Available.getID() == TopQID;
1049 }
1050
1051 /// Number of cycles to issue the instructions scheduled in this zone.
1052 unsigned getCurrCycle() const { return CurrCycle; }
1053
1054 /// Micro-ops issued in the current cycle
1055 unsigned getCurrMOps() const { return CurrMOps; }
1056
1057 // The latency of dependence chains leading into this zone.
1058 unsigned getDependentLatency() const { return DependentLatency; }
1059
1060 /// Get the number of latency cycles "covered" by the scheduled
1061 /// instructions. This is the larger of the critical path within the zone
1062 /// and the number of cycles required to issue the instructions.
1063 unsigned getScheduledLatency() const {
1064 return std::max(a: ExpectedLatency, b: CurrCycle);
1065 }
1066
1067 unsigned getUnscheduledLatency(SUnit *SU) const {
1068 return isTop() ? SU->getHeight() : SU->getDepth();
1069 }
1070
1071 unsigned getResourceCount(unsigned ResIdx) const {
1072 return ExecutedResCounts[ResIdx];
1073 }
1074
1075 /// Get the scaled count of scheduled micro-ops and resources, including
1076 /// executed resources.
1077 unsigned getCriticalCount() const {
1078 if (!ZoneCritResIdx)
1079 return RetiredMOps * SchedModel->getMicroOpFactor();
1080 return getResourceCount(ResIdx: ZoneCritResIdx);
1081 }
1082
1083 /// Get a scaled count for the minimum execution time of the scheduled
1084 /// micro-ops that are ready to execute by getExecutedCount. Notice the
1085 /// feedback loop.
1086 unsigned getExecutedCount() const {
1087 return std::max(a: CurrCycle * SchedModel->getLatencyFactor(),
1088 b: MaxExecutedResCount);
1089 }
1090
1091 unsigned getZoneCritResIdx() const { return ZoneCritResIdx; }
1092
1093 // Is the scheduled region resource limited vs. latency limited.
1094 bool isResourceLimited() const { return IsResourceLimited; }
1095
1096 /// Get the difference between the given SUnit's ready time and the current
1097 /// cycle.
1098 LLVM_ABI unsigned getLatencyStallCycles(SUnit *SU);
1099
1100 LLVM_ABI unsigned getNextResourceCycleByInstance(unsigned InstanceIndex,
1101 unsigned ReleaseAtCycle,
1102 unsigned AcquireAtCycle);
1103
1104 LLVM_ABI std::pair<unsigned, unsigned>
1105 getNextResourceCycle(const MCSchedClassDesc *SC, unsigned PIdx,
1106 unsigned ReleaseAtCycle, unsigned AcquireAtCycle);
1107
1108 bool isReservedGroup(unsigned PIdx) const {
1109 return SchedModel->getProcResource(PIdx)->SubUnitsIdxBegin &&
1110 !SchedModel->getProcResource(PIdx)->BufferSize;
1111 }
1112
1113 LLVM_ABI bool checkHazard(SUnit *SU);
1114
1115 LLVM_ABI unsigned findMaxLatency(ArrayRef<SUnit *> ReadySUs);
1116
1117 LLVM_ABI unsigned getOtherResourceCount(unsigned &OtherCritIdx);
1118
1119 /// Release SU to make it ready. If it's not in hazard, remove it from
1120 /// pending queue (if already in) and push into available queue.
1121 /// Otherwise, push the SU into pending queue.
1122 ///
1123 /// @param SU The unit to be released.
1124 /// @param ReadyCycle Until which cycle the unit is ready.
1125 /// @param InPQueue Whether SU is already in pending queue.
1126 /// @param Idx Position offset in pending queue (if in it).
1127 LLVM_ABI void releaseNode(SUnit *SU, unsigned ReadyCycle, bool InPQueue,
1128 unsigned Idx = 0);
1129
1130 LLVM_ABI void bumpCycle(unsigned NextCycle);
1131
1132 LLVM_ABI void incExecutedResources(unsigned PIdx, unsigned Count);
1133
1134 LLVM_ABI unsigned countResource(const MCSchedClassDesc *SC, unsigned PIdx,
1135 unsigned Cycles, unsigned ReadyCycle,
1136 unsigned StartAtCycle);
1137
1138 LLVM_ABI void bumpNode(SUnit *SU);
1139
1140 LLVM_ABI void releasePending();
1141
1142 LLVM_ABI void removeReady(SUnit *SU);
1143
1144 /// Call this before applying any other heuristics to the Available queue.
1145 /// Updates the Available/Pending Q's if necessary and returns the single
1146 /// available instruction, or NULL if there are multiple candidates.
1147 LLVM_ABI SUnit *pickOnlyChoice();
1148
1149 /// Dump the state of the information that tracks resource usage.
1150 LLVM_ABI void dumpReservedCycles() const;
1151 LLVM_ABI void dumpScheduledState() const;
1152};
1153
1154/// Base class for GenericScheduler. This class maintains information about
1155/// scheduling candidates based on TargetSchedModel making it easy to implement
1156/// heuristics for either preRA or postRA scheduling.
1157class GenericSchedulerBase : public MachineSchedStrategy {
1158public:
1159 /// Represent the type of SchedCandidate found within a single queue.
1160 /// pickNodeBidirectional depends on these listed by decreasing priority.
1161 enum CandReason : uint8_t {
1162 NoCand,
1163 Only1,
1164 PhysReg,
1165 RegExcess,
1166 RegCritical,
1167 Stall,
1168 Cluster,
1169 Weak,
1170 RegMax,
1171 ResourceReduce,
1172 ResourceDemand,
1173 BotHeightReduce,
1174 BotPathReduce,
1175 TopDepthReduce,
1176 TopPathReduce,
1177 NodeOrder,
1178 FirstValid
1179 };
1180
1181#ifndef NDEBUG
1182 static const char *getReasonStr(GenericSchedulerBase::CandReason Reason);
1183#endif
1184
1185 /// Policy for scheduling the next instruction in the candidate's zone.
1186 struct CandPolicy {
1187 bool ReduceLatency = false;
1188 unsigned ReduceResIdx = 0;
1189 unsigned DemandResIdx = 0;
1190
1191 CandPolicy() = default;
1192
1193 bool operator==(const CandPolicy &RHS) const {
1194 return ReduceLatency == RHS.ReduceLatency &&
1195 ReduceResIdx == RHS.ReduceResIdx &&
1196 DemandResIdx == RHS.DemandResIdx;
1197 }
1198 bool operator!=(const CandPolicy &RHS) const {
1199 return !(*this == RHS);
1200 }
1201 };
1202
1203 /// Status of an instruction's critical resource consumption.
1204 struct SchedResourceDelta {
1205 // Count critical resources in the scheduled region required by SU.
1206 unsigned CritResources = 0;
1207
1208 // Count critical resources from another region consumed by SU.
1209 unsigned DemandedResources = 0;
1210
1211 SchedResourceDelta() = default;
1212
1213 bool operator==(const SchedResourceDelta &RHS) const {
1214 return CritResources == RHS.CritResources
1215 && DemandedResources == RHS.DemandedResources;
1216 }
1217 bool operator!=(const SchedResourceDelta &RHS) const {
1218 return !operator==(RHS);
1219 }
1220 };
1221
1222 /// Store the state used by GenericScheduler heuristics, required for the
1223 /// lifetime of one invocation of pickNode().
1224 struct SchedCandidate {
1225 CandPolicy Policy;
1226
1227 // The best SUnit candidate.
1228 SUnit *SU;
1229
1230 // The reason for this candidate.
1231 CandReason Reason;
1232
1233 // Whether this candidate should be scheduled at top/bottom.
1234 bool AtTop;
1235
1236 // Register pressure values for the best candidate.
1237 RegPressureDelta RPDelta;
1238
1239 // Critical resource consumption of the best candidate.
1240 SchedResourceDelta ResDelta;
1241
1242 SchedCandidate() { reset(NewPolicy: CandPolicy()); }
1243 SchedCandidate(const CandPolicy &Policy) { reset(NewPolicy: Policy); }
1244
1245 void reset(const CandPolicy &NewPolicy) {
1246 Policy = NewPolicy;
1247 SU = nullptr;
1248 Reason = NoCand;
1249 AtTop = false;
1250 RPDelta = RegPressureDelta();
1251 ResDelta = SchedResourceDelta();
1252 }
1253
1254 bool isValid() const { return SU; }
1255
1256 // Copy the status of another candidate without changing policy.
1257 void setBest(SchedCandidate &Best) {
1258 assert(Best.Reason != NoCand && "uninitialized Sched candidate");
1259 SU = Best.SU;
1260 Reason = Best.Reason;
1261 AtTop = Best.AtTop;
1262 RPDelta = Best.RPDelta;
1263 ResDelta = Best.ResDelta;
1264 }
1265
1266 LLVM_ABI void initResourceDelta(const ScheduleDAGMI *DAG,
1267 const TargetSchedModel *SchedModel);
1268 };
1269
1270protected:
1271 const MachineSchedContext *Context;
1272 const TargetSchedModel *SchedModel = nullptr;
1273 const TargetRegisterInfo *TRI = nullptr;
1274 unsigned TopIdx = 0;
1275 unsigned BotIdx = 0;
1276 unsigned NumRegionInstrs = 0;
1277
1278 MachineSchedPolicy RegionPolicy;
1279
1280 SchedRemainder Rem;
1281
1282 GenericSchedulerBase(const MachineSchedContext *C) : Context(C) {}
1283
1284 LLVM_ABI void setPolicy(CandPolicy &Policy, bool IsPostRA,
1285 SchedBoundary &CurrZone, SchedBoundary *OtherZone);
1286
1287 MachineSchedPolicy getPolicy() const override { return RegionPolicy; }
1288
1289#ifndef NDEBUG
1290 void traceCandidate(const SchedCandidate &Cand);
1291#endif
1292
1293private:
1294 bool shouldReduceLatency(const CandPolicy &Policy, SchedBoundary &CurrZone,
1295 bool ComputeRemLatency, unsigned &RemLatency) const;
1296};
1297
1298// Utility functions used by heuristics in tryCandidate().
1299LLVM_ABI unsigned computeRemLatency(SchedBoundary &CurrZone);
1300LLVM_ABI bool tryLess(int TryVal, int CandVal,
1301 GenericSchedulerBase::SchedCandidate &TryCand,
1302 GenericSchedulerBase::SchedCandidate &Cand,
1303 GenericSchedulerBase::CandReason Reason);
1304LLVM_ABI bool tryGreater(int TryVal, int CandVal,
1305 GenericSchedulerBase::SchedCandidate &TryCand,
1306 GenericSchedulerBase::SchedCandidate &Cand,
1307 GenericSchedulerBase::CandReason Reason);
1308LLVM_ABI bool tryLatency(GenericSchedulerBase::SchedCandidate &TryCand,
1309 GenericSchedulerBase::SchedCandidate &Cand,
1310 SchedBoundary &Zone);
1311LLVM_ABI bool tryPressure(const PressureChange &TryP,
1312 const PressureChange &CandP,
1313 GenericSchedulerBase::SchedCandidate &TryCand,
1314 GenericSchedulerBase::SchedCandidate &Cand,
1315 GenericSchedulerBase::CandReason Reason,
1316 const TargetRegisterInfo *TRI,
1317 const MachineFunction &MF);
1318LLVM_ABI bool tryBiasPhysRegs(GenericSchedulerBase::SchedCandidate &TryCand,
1319 GenericSchedulerBase::SchedCandidate &Cand,
1320 SchedBoundary *Zone, bool BiasPRegsExtra);
1321LLVM_ABI unsigned getWeakLeft(const SUnit *SU, bool isTop);
1322LLVM_ABI int biasPhysReg(const SUnit *SU, bool isTop,
1323 bool BiasPRegsExtra = false);
1324
1325/// GenericScheduler shrinks the unscheduled zone using heuristics to balance
1326/// the schedule.
1327class LLVM_ABI GenericScheduler : public GenericSchedulerBase {
1328public:
1329 GenericScheduler(const MachineSchedContext *C):
1330 GenericSchedulerBase(C), Top(SchedBoundary::TopQID, "TopQ"),
1331 Bot(SchedBoundary::BotQID, "BotQ") {}
1332
1333 void initPolicy(MachineBasicBlock::iterator Begin,
1334 MachineBasicBlock::iterator End,
1335 unsigned NumRegionInstrs) override;
1336
1337 void dumpPolicy() const override;
1338
1339 bool shouldTrackPressure() const override {
1340 return RegionPolicy.ShouldTrackPressure;
1341 }
1342
1343 bool shouldTrackLaneMasks() const override {
1344 return RegionPolicy.ShouldTrackLaneMasks;
1345 }
1346
1347 void initialize(ScheduleDAGMI *dag) override;
1348
1349 SUnit *pickNode(bool &IsTopNode) override;
1350
1351 void schedNode(SUnit *SU, bool IsTopNode) override;
1352
1353 void releaseTopNode(SUnit *SU) override {
1354 if (SU->isScheduled)
1355 return;
1356
1357 Top.releaseNode(SU, ReadyCycle: SU->TopReadyCycle, InPQueue: false);
1358 TopCand.SU = nullptr;
1359 }
1360
1361 void releaseBottomNode(SUnit *SU) override {
1362 if (SU->isScheduled)
1363 return;
1364
1365 Bot.releaseNode(SU, ReadyCycle: SU->BotReadyCycle, InPQueue: false);
1366 BotCand.SU = nullptr;
1367 }
1368
1369 void registerRoots() override;
1370
1371protected:
1372 ScheduleDAGMILive *DAG = nullptr;
1373
1374 // State of the top and bottom scheduled instruction boundaries.
1375 SchedBoundary Top;
1376 SchedBoundary Bot;
1377
1378 unsigned TopClusterID;
1379 unsigned BotClusterID;
1380
1381 /// Candidate last picked from Top boundary.
1382 SchedCandidate TopCand;
1383 /// Candidate last picked from Bot boundary.
1384 SchedCandidate BotCand;
1385
1386 void checkAcyclicLatency();
1387
1388 void initCandidate(SchedCandidate &Cand, SUnit *SU, bool AtTop,
1389 const RegPressureTracker &RPTracker,
1390 RegPressureTracker &TempTracker);
1391
1392 virtual bool tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand,
1393 SchedBoundary *Zone) const;
1394
1395 SUnit *pickNodeBidirectional(bool &IsTopNode);
1396
1397 void pickNodeFromQueue(SchedBoundary &Zone,
1398 const CandPolicy &ZonePolicy,
1399 const RegPressureTracker &RPTracker,
1400 SchedCandidate &Candidate);
1401
1402 void reschedulePhysReg(SUnit *SU, bool isTop);
1403};
1404
1405/// PostGenericScheduler - Interface to the scheduling algorithm used by
1406/// ScheduleDAGMI.
1407///
1408/// Callbacks from ScheduleDAGMI:
1409/// initPolicy -> initialize(DAG) -> registerRoots -> pickNode ...
1410class LLVM_ABI PostGenericScheduler : public GenericSchedulerBase {
1411protected:
1412 ScheduleDAGMI *DAG = nullptr;
1413 SchedBoundary Top;
1414 SchedBoundary Bot;
1415
1416 /// Candidate last picked from Top boundary.
1417 SchedCandidate TopCand;
1418 /// Candidate last picked from Bot boundary.
1419 SchedCandidate BotCand;
1420
1421 unsigned TopClusterID;
1422 unsigned BotClusterID;
1423
1424public:
1425 PostGenericScheduler(const MachineSchedContext *C)
1426 : GenericSchedulerBase(C), Top(SchedBoundary::TopQID, "TopQ"),
1427 Bot(SchedBoundary::BotQID, "BotQ") {}
1428
1429 ~PostGenericScheduler() override = default;
1430
1431 void initPolicy(MachineBasicBlock::iterator Begin,
1432 MachineBasicBlock::iterator End,
1433 unsigned NumRegionInstrs) override;
1434
1435 /// PostRA scheduling does not track pressure.
1436 bool shouldTrackPressure() const override { return false; }
1437
1438 void initialize(ScheduleDAGMI *Dag) override;
1439
1440 void registerRoots() override;
1441
1442 SUnit *pickNode(bool &IsTopNode) override;
1443
1444 SUnit *pickNodeBidirectional(bool &IsTopNode);
1445
1446 void scheduleTree(unsigned SubtreeID) override {
1447 llvm_unreachable("PostRA scheduler does not support subtree analysis.");
1448 }
1449
1450 void schedNode(SUnit *SU, bool IsTopNode) override;
1451
1452 void releaseTopNode(SUnit *SU) override {
1453 if (SU->isScheduled)
1454 return;
1455 Top.releaseNode(SU, ReadyCycle: SU->TopReadyCycle, InPQueue: false);
1456 TopCand.SU = nullptr;
1457 }
1458
1459 void releaseBottomNode(SUnit *SU) override {
1460 if (SU->isScheduled)
1461 return;
1462 Bot.releaseNode(SU, ReadyCycle: SU->BotReadyCycle, InPQueue: false);
1463 BotCand.SU = nullptr;
1464 }
1465
1466protected:
1467 virtual bool tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand);
1468
1469 void pickNodeFromQueue(SchedBoundary &Zone, SchedCandidate &Cand);
1470};
1471
1472/// If ReorderWhileClustering is set to true, no attempt will be made to
1473/// reduce reordering due to store clustering.
1474LLVM_ABI std::unique_ptr<ScheduleDAGMutation>
1475createLoadClusterDAGMutation(const TargetInstrInfo *TII,
1476 bool ReorderWhileClustering = false);
1477
1478/// If ReorderWhileClustering is set to true, no attempt will be made to
1479/// reduce reordering due to store clustering.
1480LLVM_ABI std::unique_ptr<ScheduleDAGMutation>
1481createStoreClusterDAGMutation(const TargetInstrInfo *TII,
1482 bool ReorderWhileClustering = false);
1483
1484LLVM_ABI std::unique_ptr<ScheduleDAGMutation>
1485createCopyConstrainDAGMutation(const TargetInstrInfo *TII);
1486
1487/// Create the standard converging machine scheduler. This will be used as the
1488/// default scheduler if the target does not set a default.
1489/// Adds default DAG mutations.
1490template <typename Strategy = GenericScheduler>
1491ScheduleDAGMILive *createSchedLive(MachineSchedContext *C) {
1492 ScheduleDAGMILive *DAG =
1493 new ScheduleDAGMILive(C, std::make_unique<Strategy>(C));
1494 // Register DAG post-processors.
1495 //
1496 // FIXME: extend the mutation API to allow earlier mutations to instantiate
1497 // data and pass it to later mutations. Have a single mutation that gathers
1498 // the interesting nodes in one pass.
1499 DAG->addMutation(Mutation: createCopyConstrainDAGMutation(TII: DAG->TII));
1500 return DAG;
1501}
1502
1503/// Create a generic scheduler with no vreg liveness or DAG mutation passes.
1504template <typename Strategy = PostGenericScheduler>
1505ScheduleDAGMI *createSchedPostRA(MachineSchedContext *C) {
1506 return new ScheduleDAGMI(C, std::make_unique<Strategy>(C),
1507 /*RemoveKillFlags=*/true, getPostRABreakAntiDeps());
1508}
1509
1510class MachineSchedulerPass
1511 : public OptionalPassInfoMixin<MachineSchedulerPass> {
1512 // FIXME: Remove this member once RegisterClassInfo is queryable as an
1513 // analysis.
1514 std::unique_ptr<impl_detail::MachineSchedulerImpl> Impl;
1515 const TargetMachine *TM;
1516
1517public:
1518 LLVM_ABI MachineSchedulerPass(const TargetMachine *TM);
1519 LLVM_ABI MachineSchedulerPass(MachineSchedulerPass &&Other);
1520 LLVM_ABI ~MachineSchedulerPass();
1521 LLVM_ABI PreservedAnalyses run(MachineFunction &MF,
1522 MachineFunctionAnalysisManager &MFAM);
1523};
1524
1525class SSAMachineSchedulerPass
1526 : public OptionalPassInfoMixin<SSAMachineSchedulerPass> {
1527 // FIXME: Remove this member once RegisterClassInfo is queryable as an
1528 // analysis.
1529 std::unique_ptr<impl_detail::SSAMachineSchedulerImpl> Impl;
1530 const TargetMachine *TM;
1531
1532public:
1533 LLVM_ABI SSAMachineSchedulerPass(const TargetMachine *TM);
1534 LLVM_ABI SSAMachineSchedulerPass(SSAMachineSchedulerPass &&Other);
1535 LLVM_ABI ~SSAMachineSchedulerPass();
1536 LLVM_ABI PreservedAnalyses run(MachineFunction &MF,
1537 MachineFunctionAnalysisManager &MFAM);
1538};
1539
1540class PostMachineSchedulerPass
1541 : public OptionalPassInfoMixin<PostMachineSchedulerPass> {
1542 // FIXME: Remove this member once RegisterClassInfo is queryable as an
1543 // analysis.
1544 std::unique_ptr<impl_detail::PostMachineSchedulerImpl> Impl;
1545 const TargetMachine *TM;
1546
1547public:
1548 LLVM_ABI PostMachineSchedulerPass(const TargetMachine *TM);
1549 LLVM_ABI PostMachineSchedulerPass(PostMachineSchedulerPass &&Other);
1550 LLVM_ABI ~PostMachineSchedulerPass();
1551 LLVM_ABI PreservedAnalyses run(MachineFunction &MF,
1552 MachineFunctionAnalysisManager &MFAM);
1553};
1554} // end namespace llvm
1555
1556#endif // LLVM_CODEGEN_MACHINESCHEDULER_H
1557