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